also it appears that cpanel has some bugs with regard to deleting add-on domains and subdomains. for example, you can delete an add-on domain, and cpanel no longer reports it as being active. however, it never actually deletes them from the server (i.e. removing DNS entries, MX records, sendmail configuration, etc). if you go back and try to add an add-on domain that you previously deleted, it will give you the "already exists in DNS" error because it never deleted it in the first place!
subdomains have similar problems, you can delete them, but if you do an nslookup on that subdomain later, it'll still resolve.
this is really annoying and hopefully cpanel will fix it soon (matt at spenix.com was going to file a bug report with them).