to:someone from:someone subject:something
The "someone" part seems to work with full names or email addresses.
The only confusing thing is the mail search bar should switch to "Entire message" when you're using a keyword-style search rather than the "From", "To" or "Subject" buttons.
It's a very limited syntax and not well publicized but welcome anyway cause what's there works. These tests done in Snow Leopard 10.6.2 and Mail.app 4.2.