Have been doing some consulting with a small start-up company, and I got my email account with them this week. Tested it with an email to my wife's gmail address, she received it and replied and there were no issues.
Sent an email to two people at a large multinational corporation, and it got rejected. Specifically, "Remote server returned '550 5.7.708 service unavailable. Access denied, traffic not accepted from this IP"
This email is ( I think) set up through office365.
I'm not the IT guy, but I'd like to help point them in the right direction if I can, because something is fucked.