Alternatives to Gmail?

Now that I’ve moved from Google Reader to Fever, I’d like to reduce my reliance on other Google services. Switching from Google search to Bing is pretty easy, but I’m on much less sure ground when it comes to replacing Gmail.

Requirements:

• Paid service (If you aren’t paying, you are the product, not the customer)
• Search-driven interface
• Reasonable limits on message and mailbox size

I’ve heard of HushMail. Is there anything else worthwhile?

Edit: HushMail is a no-go. It doesn’t have a way to set up a filter or rule to automatically file incoming mail.