Cpanel is trying to deliver mail to the local server as the domain you are trying to send to is more than likely hosted on the same server.

When setting up the web domain Cpanel creates localdomains hence it tries to deliver to itself.

To fix simply edit the localdomains file and remove the domain in question:

vim /etc/localdomains

Delete the domain and write/quit.

I was unable to remove a subdomain from my Cpanel giving me the error:

There was a problem removing the subdomain

To fix the issue I carried out the following steps:

1. Backup the following files:

/var/cpanel/userdata/username/main
/var/cpanel/userdata/username/sub.maindomain.com
/var/cpanel/users/username
/var/named/maindomain.com.db
/var/cpanel/userdata/account/sub.domain.com
/var/cpanel/userdata/account/sub.domain.com.cache
/usr/local/apache/conf/httpd.conf

2. Remove all lines containing the subdomain from /var/cpanel/userdata/username/main:

vim /var/cpanel/userdata/username/main

3. Remove the subdomain file completely from /var/cpanel/userdata/username/:

rm /var/cpanel/userdata/username/sub.maindomain.com

4. Remove all lines containing the subdomain from /var/cpanel/users/username:

vim /var/cpanel/users/username

5. Remove all lines containing the subdomain from /var/named/maindomain.com.db:

vim /var/named/maindomain.com.db

6. Remove subdomain files from /var/cpanel/userdata/account/:

rm /var/cpanel/userdata/account/sub.domain.com
rm /var/cpanel/userdata/account/sub.domain.com.cache

7. Now we need to rebuild some files and restart apache:

/scripts/rebuildhttpdconf
/etc/init.d/httpd restart
/scripts/updateuserdomains

Now login to your CPanel interface and check the subdomain is removed.

If not try and add the same subdomain again and then remove. This worked for me.

That should be it gone.

*This was taken from http://forums.cpanel.net/f5/clean-subdomain-removal-192441.html. Step 6 was the extra step I needed to take to complete the removal.