The security database on the server does not have a computer account for this workstation trust relationship

This error is driving me crazy.  I've read a million articles on what to do to fix it.  I'm here hoping to find a magic bullet.  Here's what I recently went through.

1 The user was getting the listed error
2 I tried logging in with my user account with admin privileges worked fine
3 I went to server opened active.. users and computers and selected reset
4 Issue was the same.  So now I think  I need to go through the unjoin rejoin hokey pokey
5 Do the unjoin rejoin hokey pokey. The pc says it rejoined.  Neither I or the user can log in same error.
6 Look at extended properties for step 3.  Looks ok
7 Now I take the step of deleting the pc account from the domain along with DNS entry for the pc.
8 do the unjoin rejoin hokey poeky again because the pc thinks it joined the network
9 Try to log in with my user with admin creds and get the error "The security database on the server doesn't have a computer account for this workstation or trust.
10 check to see if computer account was created like in step 3.  It's not there.
11  Several more rounds of the unjoin rejoin hokey pokey no luck
12 CHange the PC name rejoin the pc FIXED!

This PC was not cloned, had never been on the network before (new laptop from a couple months ago) and the name was never used on the network before.  It has had this problem 3 times in two months now, and I have had this kind of issue with other PC's on the network. This is the first time I've had to change a PC name to get it working.  THat will prove to be a major pain as antivirus software is tied to PC Names as well as some other things.

Has anyone found a real solution for this.  If this happens when this PC is in the field the person will be out of luck.  I'm looking for a real solution.

THanks for any help in advance.