I use mu [1] (via mu4e) on my Mac, and it's plenty fast and has great search. Admittedly, it doesn't look like Mail.app, but it works great.

[1] http://www.djcbsoftware.nl/code/mu/