Extensive troubleshooting of somebody else's mail server seems a bit off-topic for the NANOG list. That's the sort of thing that, once the problem has been pointed out, will need to be fixed by people internal to the organization that runs the mail server.
-Steve NANOG list administration group
