I made the switch (moved 55k+ messages with http://protips.maxmasnick.com/export-gmail-to-fastmail-or-an...) and haven't looked back.
FastMail offers a similar infinite scroll feature. I was able to select and move several thousand messages through the web interface when I was first configuring it.
FastMail's highlights for me are:
- Really good, customizable "personalities" (alternate email addresses with their own SMPT servers, auto-BCC settings, etc.)
- Sieve support -- SO much more powerful than rules in Gmail, see http://en.wikipedia.org/wiki/Sieve_(mail_filtering_language)
- Customer support that actually responds and is super helpful in my experience
- Ability to use your own domain name(s) without all the overhead of signing up for Google Apps.
- Jabber support (not in-browser, but they do have a server that works with Adium/iChat/Pidgin)
- Very fast, modern web interface. Definitely faster than Gmail for me. Good keyboard shortcuts too (very similar to Gmail's but with a few differences).
- An archive folder that works well with the archive functionality in Mail.app and other clients.
The only thing that isn't great is search. It works ok for everything but searching within messages (i.e. from/to/subject searches are fine). I believe FastMail does have support for a lot more search operators than Gmail and can search headers as well. But I'm not an expert on the power user search features for either.
This is because I actually use the search in Mail.app on my Mac, which is actually better than Gmail's search capabilities for every search I've tried (same good results, but way faster). Obviously works great with FastMail too, and I figure it's good to have a local copy of email.
I also miss a few things from the (old) gmail interface, but I definitely like FastMail's interface better on the whole than the new compose in Gmail. Things I miss in FastMail are the mainly the ability to pop composing a message into a new window with one click and sync with the address book on my phone. Neither are deal breakers.
I actually use MailMate (http://freron.com) for the majority of my email access now. It's still a little rough around the edges but being able to compose emails in Markdown and see the entire hierarchy of a thread (not flattened into one level) is worth a bit of UX pain.