This is always problematic. The correct thing to do, which in many cases is impossible, is to use dcpromo to remove the domain before taking the last DC for it offline, ensuring you specify that you are removing the last DC.
Failing that, Microsoft has a KB out about removing orphaned child domains. Basically, the process is to use ntdsutil to connect to NTDS on the operations master, select the child domain to remove, and use the remove selected domain
command. Then, DS replication will occur eventually (if you have multiple DCs still, which you ought), and it should be gone.
When the domain persists even after this, you have to do a few things. First, go into the DNS manager on each DC and remove any entries related to the removed domain (SRV records and _msdcs subdomains in particular). Then, go into the domains and trusts MMC snapin and remove the trusts related to that domain. Also go to the sites and services snapin, and remove any DCs (replication nodes) that are dead and gone. In the users and computers snapin, also remove the computer and trust accounts related to the dead domain. Then, it should really be gone.