Based off of your question, I have to assume you are using Exchange 2003. If that is the case, you should be able to go into Exchange System Manager (preferably installed on a separate machine) and open up the Administrative Group, find the server and right-click/delete it. You will need appropriate Exchange permissions to do this. In my experience, that is the easiest/fastest way to do it. This is especially useful if the server has been re-imaged or wiped and you cannot gracefully take it out of the Exchange System Manager.
