What is the best way to fix registry errors without the use of a registry cleaner in XP?

I can't disagree with much that has already been said.

I'm willing to accept that your machine actually does take 10-15 minutes, by the clock. That is totally absurd.

Some people call your problem "Windows Rot". Windows just gets slower over time. It is a collection of small things that happen in the background. Yes I believe that the registry contributes to it. Using a registry cleaner is not a "magic" fix. But, it may help somewhat.

The program/process of PC care you have described is better than average.  I'd suggest adding CCleaner to it. Disk Cleanup is not bad, CCleaner is better, cleaning other stuff that DC doesn't look at. It won't make a significant difference because HD space is not your problem, but it will help a little.

"Playing" with the registry is VERY risky. If you do decide to go ahead, I would suggest you first make a full image copy backup using a utility that can be booted and run from a CD/DVD. Just in case the registry cleaner breaks your machine. 

The thing about registry cleaners is that they are taking a "best guess" at what is no longer needed. Sometimes they guess wrong. And each cleaner will clean slightly different sets of locations.  If the tool does not provide a way of backing up the registry before starting a cleanup, don't use it. It is not cautious enough.

If the cleaner offers "levels" of cleanup, take advantage of it. Work up to the most aggressive cleanup, with reboots and long runs of normal use between cleanings.

Look for a tool that also does registry "defragmentation". The registry is a database that does get disorganized by additions and deletions. Defragmenting it will re-organize it and get rid of "wasted" space, making the file smaller,  subsequently faster to read.  It is not something you need to do frequently, but since you have never done it in 5 years, it could help, after doing registry cleanup.

Another place to look for wasted CPU and RAM resources is Windows Services. These are small programs that start at boot time. They run in the background and provide support services to all apps or specific apps.  Many apps services run even though you really don't need them. You can find information about which ones you can tune by googling for "Windows XP Hardening". There are lots of sites with good information. They call it hardening because by turning off unneeded stuff, you leave fewer possible openings for the "bad guys" to attack.

I think ultimately your best bet will be simply to bite the bullet and re-install windows, and all of your apps. That is the surest way to restore your computer to almost factory fresh performance. (It won't be exactly factory fresh because you will have to add a ton of Windows Updates).

BEFORE you re-install, do 1 or more full image copy backups. At least one should be done using a tool that will easily allow you to extract files from it. Backup you data files separately to make it easier to restore them after the re-installation. IE copy them to a USB drive.

Many "experts" actually expect to, and do, re-install windows every 6-12 months!  I think it is a bit of overkill, but they swear by it.

After you do your re-install, create a full image copy
Install a firewall application (before windows updates)
After you do all of the windows updates, create a full image copy
After you re-install all of your apps, create another full image copy.

This way, in the future you have more current points to restore your computer to. It will reduce the setup time you spend to recover to current setup.

On a 5 year old XP machine, you probably have 512MB-1GB of RAM. You might also consider taking it into the shop (or DIY) and bumping the RAM up to at least 2GB, or better yet max it out.  Current versions of apps use much more memory than they did 5 years ago. Even XP will since it has been seriously patched since then.