Disclaimer: I have never experienced this problem.
Putting "local user database handle is corrupt" in your favorite search engine will turn up various threads on this subject, most of which come to the same solution you've found - reinstall the operating system (ugh!).
I found the information below at the link in the Source part of this message. I cannot verify the accuracy of the information nor can I tell you the original source.
12/18/2007
Solution: The local user database handle is corrupt
This usually occurs when you are setting up a VPN incoming connection in Windows XP/2003. It's been "well-known" for years not because of the frequencies of its occurrence, but because there is NO fix for it, and even you call Microsoft for the tech-support.
However, there is a FIX to this issue, which is to use the DOS command line. "The local user database handle is corrupt" error message doesn't cause the entire VPN configuration failed. It only gives you a hard time to select the users who will be allowed to log on to your VPN. But please do not forget one thing, we fortunately still have a DOS command tool - NETSH. This can help us in this issue instead of implementing the "terrible" solution from MS of re-installing your OS.
Here is my way to get away from "The local user database handle is corrupt":
1. Continue the creation of your incoming VPN connection (When you see the error message, just click on OK and then go NEXT)
2. After you finish the creation, you will still see a VPN connection icon shown below the Incoming Connection group in Network Connection
3. Run "cmd" as administrator
4. Type in "netsh", and enter
5. "ras show user" will list all local accounts and their RAS (Remote-Access-Service) permissions.
6. The default permission to each account should be denied by policy. To make a specific user account be PERMIT (meaning to allow the user to use VPN), use the following command:
ras set user USERNAME PERMIT NONE
7. After you press ENTER, the specified user account will be good to use.
Above steps are necessary, and equivalent to use the dialog window to select allowed user accounts for VPN service. It is better and easier to use if someone makes this in a VBs or batch file.
14-JAN-2008 update: Thanks for updated info in your problem. Sorry, I don't have any additional info nor ideas.