I third the motion regarding Fastmail. They have recently been acquired by Opera.com but that's not a negative IMO. Google apps was easier when it came along for setting up domain email but I've had excellent history with Fastmail.

Yearly plans give you the extras you'd want and are around $35/yr