I have somewhere between 15-20GB of e-mail in IMAP and Mail is quite responsive, and search is both fast and reliable.

Perhaps it's related to either your specific hardware, gmail, or Mail's support for gmail?