You can remove the stale server from AD using ADSIEDIT
Open ADSI Edit.
Expand each of the following items: Configuration Container
CN=Configuration, DC=Domain_Name,DC=com
CN=Services
CN=Microsoft Exchange
CN=Your_Organization_Name
CN=Administrative Groups
CN=Your_Administrative_Group_Name
CN=Servers
Right-click the Exchange 2003 server object which you want to delete, and then click Delete.
Reference : http://support.microsoft.com/kb/833396
Make sure that you have reassigned the responsibility (like OAB RUS) of the old server to any other server.