I looked up an old thread in the Apple Discussion Forums to find out how to rebuild my Apple Mail database and it appears to have solved numerous problems I encountered, including the situation you mentioned where Lion Mail is not searching all mail or simply fails to find mail that you know for sure is there.
To force the mail database rebuild, you will first need to navigate to ~/Library/Mail, which is currently hidden in OS X Lion. To reveal it:
1) Open the TERMINAL application in /Applications/Utilities
2) Type "chflags nohidden ~/Library" and hit Enter
3) The ~/Library folder should now be visible
Now onto rebuilding your database:
4) First, I recommend you create a duplicate copy of your entire Mail folder (hold alt/option key while dragging it to your intended copy-to destination) just in case something goes wrong.
5) Hopefully, your ~/Library/Mail folder contains only a single subfolder labeled "V2", click on "V2" then navigate to the subfolder "MailData" (you should now be at ~/Library/Mail/V2/MailData/)
6) Delete all instances of files labeled "Envelope Index" or "Envelope Index-xxx"
7) Launch your Mail application and click "Continue" at the first prompt, after which Mail should automatically begin "importing" your mailboxes.
8) After completing this process, I found that my initial search resulted in zero results. However, after about 30 seconds or so, my search results became populated and lost/missing mail now shows up.
Now that you completed this process, you may want to re-hide your User Library folder.
9) Return to Terminal and type "chflags hidden ~/Library" and hit Enter