Exim has a bunch of advantages:

• Actually written with some thought about security, so no "comedy" rootshell security holes
• Configuration files that don't look like line noise[1]
• Comes complete with an excellent filtering tool, which you can use to do some things most MTA's can't do in a tightly integrated fashion (an obvious example is to fork a message; an example of a situation in which you might want to do this is to short-circuit delivery of mail to a user's local maildrop, but also kick it out onto your ISP's relay so that it can get to them if they're not home at the moment. That's actually what the example below is for.)
• Perl bindings (though not, unfortunately, as general as you'd want -- they're pretty much just for rewriting rules.
• Written by those nice people at the Cambridge University Computing Service[2]
• Compact and comprehensible manual
• Drop-in sendmail replacement (pretty much)

1. Well, you can if you try:

# 3. rewrite certain outgoing addresses to go to local recipients also, by
# changing *only* the envelope recipient
^(.*)$  ${lookup{$1}lsearch{/software/exim-3.03/conf/map.local}{__LOCAL_AND_REMOTE__$1}fail}    T
^__LOCAL_AND_REMOTE__([^@]+)@([^#]+)$   __LOCAL_AND_REMOTE__$1%$2@${primary_hostname}   T

2. OK, maybe that's not an actual advantage

Oh... and about your "great unsolved problem" -- this sounds to me like a problem with the upstream relay. There's no reason that I shouldn't be able to emit mail from, say, "chris@ex-parrot.com", into "relay.some-service-provider.net", so long as I am doing so from "some-machine.some-service-provider.net" (i.e., a machine for which relaying is permitted through that host). The fact that the message From: line is not "someone@somewhere.some-service-provider.net" should not be relevant.

-- Chris Lightfoot, September 18, 1999

When I went to find this software I got this: Attention Post.Office Customers: As of September 1, 2001, Openwave will discontinue the sale of Post.Office* from our corporate Web site and through our sales force. We will continue to offer support services for Post.Office through Openwave’s Technical Assistance Center (TAC) for an additional twelve (12) months with support ending August 31, 2002. openwave apear to have taken software.com as given by P. Greenspun in the link at the head of the article.

-- Laurence Cuffe, October 4, 2001

Personally, I install Postfix whenever I needs a MTA. Postfix seems to be the best alternative to Sendmail. It provides Sendmail compatibility, in a more secure and modular way, with a configuration that is clear to understand. Postfix is also lighter when it comes to system load.

I used Postfix as a SMTP gateway for a 2000 active mail users messaging system. It was trouble free.

-- Hubert Figuiere, March 12, 2002

• Postfix mailer home page- Home page for the Postfix MTA   (contributed by Mike Fischbein)

• Unofficial qmail home page- Very comprehensive listing of stuff for the qmail MTA. Links to all the official stuff from Dan Bernstein as well as hundreds of contributed fixes, enhancements, tips, FAQs, etc etc etc.   (contributed by Matthew Brown)