I found a brilliant little gem in the MailMate menus: you can change what MailMate searches by default! For a while now I've been frustrated by the default search because it only searched the “from” field of my emails and I generally just want to search everything. So, I set up my search with to look through the “Common Headers or Body”:
And then hit the button:
Simple enough, but it alleviated some pain for me.