The first thing to consider in all sudden changes like this is to ask “What changed?”.
You mentioned your domain mail server – Is it under your control, or that of your ISP? Ask the mail folks if they’ve had any policy changes, or or mail server organization changes.
Have you made any changes? Have there been any security changes in your organization such as an firewall-based email proxy which is masquerading as the domain mail server? To test this, a trace-route style program like firewalk, which uses the actual service ports, can show you if the hop count is wrong.
Have you looked through the syslogs to see if there is additional information that would shed light on this?
Write back with more information, or, if any of this points you to an answer, write back (to the group) and let us know what it was – so we can all learn.