How to remove alternative NetBIOS name

We renamed a Windows 2008 R2 x64 server.

We renamed it by running

 netdom computername oldname /add:newname
 netdom computername oldname /makeprimary:newname
 netdom computername newname /remove:oldname

REF: http://technet.microsoft.com/en-us/library/cc835082.aspx

This was done in a staged manor over a couple of days with reboot's and other configuration changes to keep services up as much as possible while changing the server's name. From the point of view of active directory everything worked. The object in users and computers has changed name, their is no reference to oldname in the AD Database (I spent hours searching in ADSIEdit) and the DNS records are correct. We have even checked the system name table with

C:\Windows\system32>netdom computername newname /enumerate:ALLNAMES
All of the names for the computer are:

newname.ourdomain.local
The command completed successfully.

and this shows the single new name :)

However..... The server still responds over netbios to the oldname and the newname. We tracked this back by doing a network capture and proving that it was responding to the old name. After that we ran

C:\Windows\system32>nbtstat.exe -n

OURDOMAIN:
Node IpAddress: [10.x.y.z] Scope Id: []

                NetBIOS Local Name Table

       Name               Type         Status
    ---------------------------------------------
    NEWNAME     <00>  UNIQUE      Registered
    OURDOMAIN   <00>  GROUP       Registered
    NEWNAME     <20>  UNIQUE      Registered
    OLDNAME     <20>  UNIQUE      Registered

outputs modified for obvious reasons.

We have looked in the registry and neither of the following keys contain the oldname

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\LanmanServer\Parameters\OptionalNames
or
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\ComputerName\ComputerName

EDIT: In response to a great idea from @Rex

setspn -L newname
Registered ServicePrincipalNames for CN=NEWNAME,OU=Servers,OU=Site1,DC=ourdomain,DC=local:
    SMTPSVC/NEWNAME
    SMTPSVC/newname.ourdomain.local
    TERMSRV/NEWNAME
    TERMSRV/newname.ourdomain.local
    WSMAN/NEWNAME
    WSMAN/newname.ourdomain.local
    RestrictedKrbHost/NEWNAME
    HOST/NEWNAME
    RestrictedKrbHost/newname.ourdomain.local
    HOST/newname.ourdomain.local

This is puzzling. Does anyone know how to remove OLDNAME from the systems netbios identity? Or even any way to progress our diagnosis?


I'll throw this in an answer just in case it slipped under the radar as a comment. Apologies ahead of time if you saw it already and it doesn't apply to your situation...

Can you double-check HKLM\SYSTEM\CurrentControlSet\services\LanmanServer\Parameters\OptionalNames? I just followed your steps and found OLDNAME was still present in the output of nbtstat. I searched the registry for instances of OLDNAME and found three. I then renamed each to different unique values, rebooted, and ran nbtstat again. The value in OptionalNames is now in the output of nbtstat along with NEWNAME. I was even able to add a tertiary name to the output of nbtstat by adding another value to OptionalNames (it's a REG_MULTI_SZ).