Malformed or unexpected name server reply on all outgoing emails

Hey guys,

Emails have been working perfectly for months, but for the last few weeks I've been constantly getting the following error on most outgoing emails

(Name service error for name=mail.example.com type=A Malformed or unexpected name server reply)

Any ideas what it could be? If I jump onto linux and ping mail.example.com it'll come back with the correct IP number

Double-check your DNS settings at server and Registrar, looking for typos.

Checked and double checked. Has been working and not changed anything other than updates for many months... everything else works, can ping the domain from the Linux prompt.. is only email that's being effected.

Your CWP nameservers haven't mysteriously reverted to the defaults per chance?
Also, check them in your CWP DNS records for the user domains.

Just checked! Yes they're still the same as they should be and there's DNS entries for them in the zones file

Interestingly enough emails seem to be going out to @gmail.com addresses (I don't have many email addresses to test with that aren't sitting on the server in question)