Inbound is easy because our EXTERNAL address for Outside 1 (SMTP) would me the MX record. Do the same for outbound requires a little more thought. I would probably look at policy based routing however this would require a router in order to implement. If this is not a problem simply put a router on a SINGLE outside interface with both upstream providers connected, configured a routing policy for SMTP and implement NAT on the SMTP line - then presto your mail is coming and going down one of the lines :)
Info on policy based routing.
http://www.cisco.com/warp/public/732/Tech/plicy_wp.htm
Hope this helps.