Which callout are you using to deregister the DNS when VMs are normally decommissioned? If you use the right callout, this should also be called when a VM is rolled back on failure. I can't check which one we used specifically at the moment, but it worked for us.
The only problem that we had was with DNS caching IP addresses. IN this case, after the rollback BNA then allocated the same IP address to the next VM that was provisioned, but DNS still had an entry for the previous (failed) VM in the cache. We haven't figured a way to get around this one yet ...
In theory, you could request a DNS cache update, but that is not very efficient if you have to do it for all IP removal requests.
VirtualGuest_DECONSTRUCTOR should do it I think.