I'm using my gmail with Mail. I wanted to find an email I wrote a while back that had the prescription for my contacts in it. Searching for this using spotlight in Mail wouldn't find it - when I knew it was there since I can search for it via the gmail web interface. I know the message is on my Mac.
Also, when you select 'Entire Message' as the search option it sometimes seems to miss searching the subject line (am I being stupid in thinking that 'entire message' means the subject, sender, receiver, and content?)
So my thought is that Spotlight has not properly indexed these emails, I hope that's the case and that it's not just Spotlight having a pretty big bug here. Now to find out how to re-index stuff...