I use a Dane Elec 4gb (kmart 11.99 sale) and a PNY Attache 512mb (free craigslist) for my Win7 Ulitmate readyboost.
Any newer major name (PNY,Dane etc) should work.
I did see a compatibility chart for usb drives for vista one time by googling it.
Definitely format with Fat. I used exFat for mine.Newer and a little quicker file system according to benchmarks.
also when you first plug in and check readyboost it might say fail but use the test option. On my PNY it said failed then I tested and it is fine.
Also according to Vista benchmarks it really didnt make a difference unless you were below 2gb or so of ram.
I havent seen any Win7 benches ( i googled and none came up) but if you have 2 or more gigs then it isnt really anything to worry about.
Apps do seem to launch a split sec faster but that is hard to measure.
I have 2gb so I use it.I figure it cant hurt.