Gmail. But I may have solved my own issue. It seems like the MX servers may still be propagating and I just need to wait a bit longer before complaining about anything…would that make sense?
If so, please expand each entry, to see extended error information, and share it here.
I don’t know how long you waited, but DNS propagation can sometimes take quite a while.
So it isn’t impossible that the sender’s infrastructure may have been stuck with stale MX records, leading towards your old provider, or otherwise no MX records for a little while, if you didn’t have any before.