Google "250-XXXXXXXA asa cisco starttls" and you'll find this is almost certainly an ASA preventing TLS as configured on the device. Since it doesn't want TLS traffic, the config is to just mangle the packets. Well known effect, been around for years (5+). The FW admin needs to correctly deploy fixup, allow TLS or simply not inspect esmtp. Simple fix, documented in Cisco doc 118550, among many other places.
You beat me to it. That's the first thing that popped into my head, too. This (for some inexplicable reason known only to Cisco) is the *default* behavior of ASA and PIX firewalls, so really it probably just means that someone that didn't know what they were doing threw a firewall in the mix somewhere. It's an easy fix, but requires messing with policy-maps, which inexperienced admins often find confusing.
At a former job we were having mysterious DNS problems.
I finally discovered an ASA was the problem.
The boneheaded thing was defaulting to dropping any DNS packet with the EDNS0 option enabled.
EDNS0 had been around for *five* years, and we were running the latest firmware.
If a fw vendor can't be bothered to keep up with the protocol standards, they shouldn't be interfering with the application layer.