というわけで、Windows版のVimはfindstrコマンドを呼び出してるわけですが、grepもインストールしてれば使うことができます。適当にこの辺などから取ってきてgrepをパス上に置いて、次のようにvimrcに書けばＯＫです。
"Use grep in Windows
set grepprg=grep\ -nH
ところで・・・grep-2.5.1はマルチバイト対応しててナイスなんですがちょっとバグってるのが嫌な感じです・・・。"Re: bug report on GREP" によれば0x815B、shift_jisで言えば「ー」がダメなようで、あまりダラダラした文章を書いてはいかんということですなー（←禁止）。
あと補助的に、lvのlgrepも入れてみました。これはshift_jisでもeuc-jpでも自動認識してgrepしてくれるらしいというので実は本命だったんですが、再帰検索できないのと、ファイル名を単体で指定するとfindstrファイル名を出力してくれず、grepの-Hに相当するオプション（ファイル名を出力する）も無かったので、こちらの方々のようにソース追いかける気合も無いので、残念ながら諦めました。