Removing the original DC is easy and it seems like you’ve done your homework so you know how to move all the roles, etc. I would just use a different name for the DC to avoid trouble and then just create another static DNS A record that points the old DC name as well as the new to the same IP. No problem there- any host looking for the old name will still hit it just fine.
If you want to use the same name, you do need to make sure that all the objects are out of AD and again, it looks like you’ve done your homeword on this. Just run ADSI edit and make sure it’s 100% clean, the check DNS (And WINS if you have it) and make sure every trace of the old server name is gone then bring up the new server with the same name.
The DNS server settings in the other DCs and DNS servers don’t really matter so much as long as they have one working DNS server. The DNS server search order is determined by which DNS responds quickest over time by an algorithm on the DNS client.