I used telnet and was able to connect to 5 out of the 6 I tested. The one that seemed questionable, I wasn't able to ping the domain at all.
Of the 5 success, 4 responded immediately with a 220.
The other was blank, but then when I tried to type something else into the box, I got a 220 barracuda.bdlaraway.com.
The client that started me investigating owns 2 of the 6 I'm testing. He indicated that he used to be able to email these clients without issue. I confirmed that as of 12/20/18, my client could send mail to both of these domains without error.
None of our hardware has been changed recently. I'll have to check to see if there are any firewall changes.