I often find that I need more than Mail's basic search. For example when I want to find an email from "Fred" with "Foo" in the title that has an attachment, etc. My usual method has been to create a Smart Mailbox, find the email I was looking for, then delete the Smart Mailbox.
It just occurred to me to keep the Smart Mailbox and name it "Advanced search..." Now I have an an advanced search in my Mail sidebar. To edit just double-click the mailbox icon and enter new criteria. As a bonus, my last search is always saved.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20071115193741157