Ask HN: Best host for e-mail servers/mailman?

I've inherited a spaghetti mess for our e-mail servers. We currently have two e-mail hosts, which require awful hacks to get to work together.

Both hosts also have a pretty bad blacklisting problem.

We're starting to switch to webfaction, but webfaction doesn't easily allow you to have your own instance of mailman running.

I'm thinking about paying for a dedicated host for our e-mail servers, which would also ideally have its own instance of mailman installed and a large number of lists and outgoing e-mails allowed. This host would not have a blacklisting issue.

However, I haven't been able to find any reputable recommendations for such a host. Many run-of-the-mill shared hosting plans offer mailman through cpanel, but these are exactly the kinds of hosts I've had issues with.

Has anyone worked with a host that does e-mail servers really well?