I hope this is considered operational...

A new customer of ours, blah.com, was using a different (unnamed) network
for dns services. This other company had messed up the dns zone, with a 1
year ttl in some of the dns records. The domain has been transferred to our
dns servers, with correct settings. Various disparate networks are
unfortunately using the old cache entries. Short of emailing each network
as we find the problem (usually by email not getting through), or asking the
old mx ip owner (critical path) to forward the mail from their smtp server,
is there anything else to be done?

Hmm, just checked, and the old provider is still lame hosting the dns zone,
even though it isn't authoritative. Perhaps they just like it that way.