Having read a previous poster's great suggestion for the use of Apple regular expressions in Spotlight, I thought I'd try it with Mail 2.0 Smart mailbox feature. I had a Smart mailbox that included all mail messages with xxx ANYWHERE in the Message Body. That worked well, until I realised that it excluded a few messages that could be identified just by their 'From' field.
I then edited the Smart mailbox definition by clicking on the '+' and adding From contains YYY. But the result of this is a logical AND, so that the result was it would only give me messages that contained 'xxx' in the message body AND 'YYY' in the From field.
I then edited the Smart mailbox definition to read xxx | YYY anywhere in the message, and sure enough, it found the complete set. I'm sure you can extend this with OR and NOT, but I don't know the regular expressions for these in Apple's new scheme.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20050515160424368