I've been on Fastmail for at least the last 7 years and find it to be an extremely reliable service. I've probably used them as the MX for over 20 domains.

I am migrating away from them however, because I've decided to consolidate all my hosting with a single provider (Linode). I can wholeheartedly recommend them though.