Sounds like EFS.
EFS restoration is indeed a trip and paying your penance at www.lostpassword.com
EFS does require use to backup the EFS key for the day we need it.
Consider this to be like locking your car keys in a car or losing the last key to the car and having a new key made. Costs a little and you learn to keep a spare copy. Here's the article about making the spare EFS key copy.
There should be an article for XP, 7 but this is done before the formatting.