I've just noticed something strange. Mail will only show results of a search if you have actually viewed an email with that search text in it.
Eg,
The word username
This was in an old email and I wanted to find the email referring to it. It didn't show in mail search.
I eventually found the email manually and looked into it. Then, when I used the search in Mail again for the same term, the email was found. This happens almost everytime.
Is it just me or has anybody else got the same problem? I forced spotlight to do a re-index but the same problem remains. It even happens with emails that I've sent today. They don't show up until I've actually viewed them.