Ask HN: Email for Startups?

We are setting up our Linode as a required step for launch; the DNS A records are propagating now, but I'm staring at the MX records thinking "crap...I don't want to manage a mail server."

I could use GMail For Business (or whatever they call it), but my experience with that is poor. As per standard, they use headers like this:

From: joe@company-name.com\nSender: joe@gmail.com

Unfortunately, the most common email client on the planet, Outlook, will display the Sender field in preference to the From field, so you look pretty unprofessional to Outlook users.

Are there particular hosted providers that people recommend? Or are we really stuck dealing with it ourselves?