I understand what the OP is talking about. Mail search, at least for couple days, was completely useless to me. I could see an email in my inbox, go up to search and type a term from the message body and the message would not come up in the search results.
Or, I knew I had received and email from someone a couple days ago, and started to type in the domain name of their email address, and it wouldn't come up. But I could manually scroll through my inbox to go find the message.
So search was not properly indexing the emails. I had posted several messages in this forum regarding this problem. Then, lo and behold, mail search started working properly for me just last night. Not sure what the issue was, except it seems as if Spotlight hadn't completely indexed all my mailboxes or something. But it's just odd because I installed Lion the day it came out and only last night did mail search finally start working for me........