I have seen this error "The operation failed due to a registry or installation problem. Restart Outlook and try again. If the problem persists, please reinstall." pop up twice in the past few weeks. After researching the error online I found numerous posts pointing to Microsoft Knowledge Base Article KB315048.
The solution as told in KB315048 is to create a new Outlook profile with for the user. This however did not fix my problem. I tried doing a "Repair" on Microsoft Office XP once and did a full uninstall, reboot, install of Microsoft Office the second time in an effort to fix the issue (as that is what the error clearly states). Neither of these options worked.
After searching and searching for a solution I tried something different. I rebooted the Microsoft Exchange 2007 server. That did the trick. First I had tried to restart the Microsoft Exchange Information Store Service, but when that failed to stop I had no choice but to restart the entire server.
From what I can tell the problem we had started when the power kicked out and back in really quick. Our Microsoft Exchange 2007 server stayed on due to its UPS as did the workstation, but something went wonky somewhere along the line.