A few ideas, scans with registry cleaners will always find "errors", so by itself that doesn't mean anything.
You don't mention the model of the laptop, don't HP have a built in recovery partition usually accessed by pressing F11 before windows loads and usually the extra option for the user to make recovery disks in the event of problems with the built in partition. Using the F11 would be a destructive installation, all owners data, music , pictures etc, would be lost and the machine would be as when it left the factory.
Did this problem suddenly happen? Makes it sound possibly malware. There is only one anti-virus program on the laptop? What program is it?
Have you tried a System Restore? Some infections will carry through system restore, however have you tried a restore?
Have you booted into Safe Mode to see how it performs, usually keep pressing F8 key up and down rapidly after first switching laptop on and before windows loads.
You could try setting the bios to boot from CD first and running a boot cd anti-virus before windows loads something like
or maybe boot into safe mode with networking and download the free MBAM, update and run it.
Any frequent errors showing in Windows Event Viewer
You don't mention when the laptop started going wrong and exactly how old it is but if it's a software problem including malware the repair or replacement warranty probably wont apply.