The way I got around this issue was by letting sendmail listen on port 25 as usual, but having a iptables rule that redirected all incoming connections on port 25000 to 25.

Hey, great idea, quick and easy and no sendmail voodoo. iptables -t nat -A PREROUTING -p tcp --dport 27 -j REDIRECT --to-port 25 iptables appears to do the prerouting change first then run the normal port 25 rules on the altered packet. Perfect. Then Outlook Express clients just change: Tools -> Accounts -> <your mail account> -> Properties -> Advanced -> change outgoing mail SMTP number from 25 to 27 iptables is my hero!