Rename AD computer member fails with "Cannot create a file when that file already exists"

I'm trying to rename a workstation that was joined to our domain last week. It's been rebooted at least once since then.

My domain is based on Windows 2012 R2 and the members in question are running Windows 10 Pro. In case it's useful information I have three DCs (and, yes, they are synchronised).

The rename works most of the time:

$aa = Get-Credential [email protected]
Rename-Computer -ComputerName mynewpc -NewName alpc001 -DomainCredential $aa
WARNING: The changes will take effect after you restart the computer mynewpc.

But I have a couple of machines which stubbornly refuse to allow the rename:

Rename-Computer -ComputerName otherhp -NewName alpc005 -DomainCredential $aa
Rename-Computer : Fail to rename computer 'otherhp' to 'alpc005' due to the following exception: Cannot create a file when that file already exists.
At line:1 char:1
+ Rename-Computer -ComputerName otherhp -NewName alpc005 -DomainCredent ...
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : OperationStopped: (otherhp:String) [Rename-Computer], InvalidOperationException
    + FullyQualifiedErrorId : FailToRenameComputer,Microsoft.PowerShell.Commands.RenameComputerCommand

Here's another attempt:

netdom renamecomputer otherhp /newname:alpc005 /ud:contoso\administrator /pd:*
Type the password associated with the domain user:

This operation will rename the computer otherhp
to alpc005.

Certain services, such as the Certificate Authority, rely on a fixed machine
name. If any services of this type are running on otherhp,
then a computer name change would have an adverse impact.

Do you want to proceed (Y or N)?
y
Cannot create a file when that file already exists.

The command failed to complete successfully.

There is no computer (or other account) with this new name, and there's no entry in the AD DNS for it either.

The additional error report from $error[0] | fl -f as requested in a comment is as follows:

writeErrorStream      : True
Exception             : System.InvalidOperationException: Fail to rename computer 'otherhp' to 'alpc005' due to the following exception: Cannot create a file when that file already exists.
TargetObject          : otherhp
CategoryInfo          : OperationStopped: (otherhp:String) [Rename-Computer], InvalidOperationException
FullyQualifiedErrorId : FailToRenameComputer,Microsoft.PowerShell.Commands.RenameComputerCommand
ErrorDetails          :
InvocationInfo        : System.Management.Automation.InvocationInfo
ScriptStackTrace      : at <ScriptBlock>, <No file>: line 1
PipelineIterationInfo : {0, 1}
PSMessageDetails      :

I don't have any IT support in the user's office, so we do as much as possible remotely. If all else fails I suppose I could grant enough privileges to the end user to unjoin their PC, rename it, and join it back again. But I really don't want to do that if there's a realistic alternative.

Suggestions gratefully received, thank you.

I've been asked for the output of NETDOM QUERY /Domain:{domain} WORKSTATION from each DC. The PC appears in the list for all three; here's a snippet from the results:

PS C:\Windows\system32> NETDOM QUERY /Domain:contoso.com /Server:DC1 WORKSTATION
List of workstations with accounts in the domain:

ALPC004      ( Workstation or Server )
...
OTHERHP
...

The PC in question (OTHERPC) does not have the ( Workstation or Server ) clause - but many of my PCs don't have this, either.