A domain controller that we had as part of our forest suffered a major hardware failure where the all drives were lost. No backup was done because it was yet to be implemented to its proper site. I have deleted all objects related to it with the exception of the object under the domain cotrollers. My question is whether I can delete that object and have a new machine built under the same computer name or do I delete it rebuld the DC under a different name? As part of our naming convention I would like to have it done under the same name. Is that possible?

Sure you can, what matter is SID not the computer name, so you can safely remove that machine from DC OU and then join it again under the same name ....