Try telnetting to port 25 and sending a raw test message. If you get the same error, it's not Mail::Sendmail that's causing the problem.

For I doubt this is not so much a Perl question, rather more of a question on how your MTA is configured. I would look to its logfiles for more information. The fact that it's a class 500 error, rather than 400, means that the problem is permanent, not just temporary. This would tend to rule out transient DNS errors (e.g. nameserver not responding).

If it's DNS, it could be ChangedTheDomain.WhatEver has been zapped in the DNS, either lacking MX or A records, or a firewall was reconfigured over-strictly, or someone is playing with stuff like RMX or SPF.