How can I fix Lion Mail's search functionality?
I had the same problem and it turned out the index was broken.

A rebuild didn't work for me so I had to quit Mail and type (in the terminal):

cd ~/Library/Mail/V2/MailData/
rm -rf Envelope\ Index Envelope\ Index-shm  Envelope\ Index-wal


After that, reopening the Mail app took some time for the index to rebuild but it fixed the search index.

Thanks to MacRumors for the answer