I narrow it down to the simplest test case. They actually left the file in my home directory that they used to test PHP email after the migration. Still had their technician's email addy in it.
I called them, got a tech to look at that file. He started looking at my MX records. I explained why that wasn't it. Said he'd forward the ticket to programming. I explained why that wasn't it.
Told him that most likely it was a sysadmin issue. Either someone had changed the sendmail configuration on the webserver, or they had changed a routing rule between the webserver and the internet. And it had happened between 8:30 (last confirmed email sent) and 10:30 (when I noticed the issue) last night.
He writes it all down and says they'll email me in the morning.
Twenty minutes later, I get an email from that little test file. And now my other apps seem to be sending again. I wonder what the email tomorrow morning will say? I wonder if I'll even get one?