Change in behaviour for relay.force9.net?

[#1]

I have a domain which I use mainly to make handling email easier - I can make up a new email address on the spur of the moment to use with companies who 'need' my email address for some reason. I also use gmail as my mailbox - but then use relay.force9.com as the smtp server through which I send all my email.
This has been working fine for years now, but as of today, something seems to have changed and I can no longer send email. I get the following error returned:
Delivery to the following recipient failed permanently:
    xxxxxxx@xxxxxxx.com
Technical details of permanent failure:
Google tried to deliver your message, but it was rejected by the relay relay.force9.net by relay.force9.net. [212.159.8.104].
The error that the other server returned was:
550 <yyyyy@yyyyy.com> sender rejected - invalid domain (no MX or A record)
This error seems to have been generated by relay.force9.com, but I'm not sure why - it implies there is no MX or A record for my domain (represented by yyyyy.com in the above error), but nothing has changed on the domain record - so I'm thinking something has changed on the relay.force9.com server maybe?
Anyone have any clues as to what has happened?

[#2]

The message implies that if you run

nslookup -type=ANY yyyyy.com

at a command prompt then no MX or A record will be found. This means it is an invalid sender domain and the recipient's mail server has refused to accept the message.
If the domain does have an MX or A record, is the local part of the sender address (before the @)  a valid mailbox?

[#3]

Thanks for the reply. I think I solved it. Having checked my domain it was as if it didn't exist - DNS lookups failed despite the DNS records appearing to be correct.
It turns out the domain was temporarily suspended by ICANN for having an incorrect email address (the same deliberately invalid one it's had for 11 years now)
Apparently they now insist email addresses are valid and they (according to UKReg/Fasthosts) now enforce verification of the address. They did that recently for me and as I never saw the email, it got suspended. Having changed the email address to a valid one, I have been able to validate the new address and the domain should be reactivated.
So, nothing to do with Plusnet!
On the downside, I'm about to get a lot more SPAM.