My search doesn't bring up all applicable messages...

Mail is only indexed once a day, any messages that you have received today will not show up in the results when you do a search, until the next day.