I have something similar as well.
I have a client who is trying to add an addon domain but it gives an error that it's already set up. There's no DNS zone and it's not listed in cPanel, so where else would I need to look to remove it so I can add the addon?
Is this the same issue you're having?