CNAME Email Bounce Back Errors

The Non-Profit I work for uses IXWebhosting for our webhost and to manage email accounts. For the past 2 months whenever we send emails to anyone @baaqmd.gov, we receive CNAME bounceback errors.
I have contacted IXWebhosting and they say that their DNS server's aren't registering baaqmd.gov and that I need to contact baaqmd.gov. Well I've been in constant contact with baaqmd.gov's IT guy and they are receiving emails just fine from outside agencies. In fact, when I send a test email using GMAIL to baaqmd.gov, they receive it just fine.

To further confuse me, we receive emails fine from BAAQMD.gov.