We too are having similar problems. Only customers that emails route through messagelabs servers. They can send to us but our replies never get there.
Can see a successful connection on our SMTP logs on our outbound mail server. Had two customers last week with the issue but received bounce backs. Now no bounce backs but more customers.
Let us know if you have a resolution.
Thanks