hmmm....interesting.
I guess in your shoes I would be looking at any assumptions I had made.
Does the SMTP send service on the Messagelabs servers use the same IP address(es) as the SMTP receive service, for which you have the routes setup on the switch?
Can you see your SMTP logs on both sides of this issue, to see if,
a/ The Messagelabs is definitely initiating a connection to the EMail server, and getting nothing back?
b/ Does the email server see the SMTP connection but reject it due to - perhaps - DNS changes you may have done in relation to implementing the new firewall?
I'm also thinking about the topology on the outside of your two firewalls - do they share an outside segment?
How does incoming traffic know which path to take?