Get a second (additional) server and set it up as the mail host for the domain in question.
The problem you're going to run into using a single server is that all outgoing mail is going to go via the same route, and likely mapped to the same public IP address by your NAT device (firewall, router, etc.) therefore there's no trivial way to differentiate outgoing mail from domain1 vs domain2, as far as the public IP address is concerned. The only way to do that is with a second machine, with a separate NAT rule at your network edge.
I'm confused, Smoke - how does that help the original poster's question?
MX records in DNS handle incoming mail routing - i.e. where remote mail servers will attempt to deliver mail for any given domain, but the OP wants separate addresses for each domain. Multiple MX records won't help with outgoing mail, and all outgoing traffic from the server will have the same public IP address.