And if you have GMail, you can patch it to do server-side search as well:

http://people.spodhuis.org/phil.pennock/software/mutt-patche...

Still, I like Mail.app better, since it supports multiple accounts well and has excellent search.