I think they may have for got to set the DNS record correctly when they did the MX record. You should run that message by them and see what they say about it. Here's an exaplnation:
1) We scan every domain's MX records 3 times per day, and sometimes we can't find that matching record at the DNS Host, so you see that error message.
2) When we scan later, if we pick up the MX Record, we automatically "refresh" you settings and remove the domain from the pending state.
3) In order for your domain to be cancelled because of this error, our servers would have to fail to find your MX record 90 times, something that is extremly unlikely to happen, and considering you would probably log in as admin at least once a month you can also refresh manually
4) If your MX record at your registrar is still correct, even if we can't find it, you will still be able to send and receive mail. All this problem affects is our recognition whether the domain is registered properly or not.
This is a problem for your hosting provider and it looks like it happens a lot.