I don't buy the "we need open relay for nationwide users" argument, either. Build a cheap MX that does nothing but take mail from a given POP, and send it to the world. Anti-spoofing at the border, don't accept mail from the outside world, and you're done.
You must not have a roaming staff or are willing to keep telcos wealthy.
Roaming staff usually needs some form of VPN access, anyway, and even if they don't, this is a great use for one. Put a VPN client on the roamer's computer (Linux, Mac, and Windows 9x/NT/ME/2k all have IPSEC capable clients available), then use the VPN to get back to the mail relay. If the mail relay is behind the VPN tunnel termination point at the server end, then it should only accept mail for relay from valid VPN clients. As such, you solve the roaming staff problem without an open relay. VPN boxes like Ravlin and Nokia Crypto Cluster are cheap enough today that I would consider it a valid cost of doing business if you don't have a better solution. Owen