I am sorry I have to mention Toshiba. It can probably happen to any other brands, but so far I had only been able to see Toshiba ones which actually happened.
Before I go on, let's put this straight. If the packaging says its Vista Readyboost compatible, it should be. Otherwise, no matter what you do, it will probably not be. Notice I mentioned probably, because I had a red Sandisk flash drive which actually IS compatible, but is not advertised as such.
The only problem arises when you actually plug in the flash drive and found that Vista complain it does not meet the minimum requirement. Btw, I had mentioned before, the requirement is only 2MB/second.
I was very upset when I gotten the Toshiba drive and found that I was ripped off. The biggest problem was I bought the 4GB drive solely for the purpose of Readyboost. 4GB is the max you can go on Windows Vista, but do note that in the future in Windows 7, this limit has been removed. Next, when I attempted to RMA the item, Toshiba told me that it was from an "unauthorized" dealer and advise I go back to the shop I bought from, which turns out to be Playcraft. They are only located in the far west, which will probably cost me more than this flash drive to go.
So, I had to take the matter into my own hands. I was so frustrated I thought I might as well "destroy" the drive by overwriting it with zero or something similar using a DOS hard disk wiper tool. And that I did. There are many which you can use, I used Acronis in this case. What I did not was to create the partition back.
I booted back into my Windows Vista and it detected the unformatted drive. I simply create a "simple volume" and remount the drive with a drive letter. Suddenly and "automagically", Readyboost prompt pops up saying it is ready to be use with Readyboost.
Unbelivable? I think so too. And I really wondered what they did in the first place that made the drive NOT Readyboost compatible? Maybe I should had checked the drive before I did the HDD wipe on it... In any case, I hope this helps you out there solve similar problems.