I was stunned to find out that the search function on the Mail.app wasn’t working anymore since I’ve upgraded my Mac from Snow Leopard 10.6.8 to (the very cool) Lion 10.7. Thought it could be Spotlight not working, or something else.
Well, as it turns out, it’s a combination of 2 problems:
1) turn Spotlight indexing on:
sudo mdutil -i on /
2) when using IMAP, configure your account to Keep a message for viewing offline
That’s it! Where Snow Leopard was able to search thru already downloaded mail (although the above option was enabled), Lion can’t.
Now the search is working great!