It's the mailhost being blacklisted, almost certainly. We use Sprint which is hosted by Frontbridge. That poor company has been passed around from owner to owner and the service has gone up and down. They were at their worst when owned by Microsoft.

Now that they've been sold on, they seem to be getting better. Still, due to the nature of the service, the servers do get blacklisted because of the volume of outbound mail (and the fact that some of the 'tenants' do undoubtedly send spam and/or volume mail that is incorrectly flagged as spam). This is one of the hidden 'gotchas' about using hosted mail services. Fortunately the blacklistings clear up within about 24 hours or so.

What you can do is sign up for a new host and point the MX record there. Check with your DNS provider on how long this takes to update. Some are instant, some take 24-48 hours, some can take longer. So long as you don't discontinue the old accounts prior to the change, you should be ok. Just ensure you have a 'backdoor' webmail login (e.g. webmail.'inserthostingcompanyhere'.com) you can log in with your account info so that when the MX record DOES change you can go in and look for 'orphan' emails.