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!