I finally have gotten this fixed after many, many frustrating weeks. My printer is an L7650, but this process may work for you.
First of all I had to do a complete Level 4 uninstall, which is one level lower than the HP service people initially told me. I didn't even know what an L3 uninstall was before I started this process. Since my printer is different, see if you have an L4 uninstall procedure. The Lx uninstall procedures are not executable from the standard install GUI, but rather in a subdirectory on the cd: \util\ccc\uninstall_lx.bat, where the x is the level you are going to uninstall to (e.g. uninstall_l4.bat).
But that was not sufficient. It was just the starting point. I also uninstalled all HP printer/scanner software on the systems (i.e. for any other HP printer or scanner devices) using the add/remove software control panel software (this system used to have another HP printer attached). And then I also had to go through and manually delete the Program Files\HP directory, as well as several hpq*, hpw* and hpz* files in the \Windows and Windows\System32 directory and also the referencing entries in the registry. Also I scanned *.inf and *.pnf files looking for references to HP printers and scanners. These were done more as a "hit and miss, the scanner still isn't working", "let me continue to delete files (with reboots) until all remnants are gone" simplistic mentality. A number of the hp* files kept on reappearing after rebooting (I suspect these were due to the remnants of older HP software that really was never cleaned up). When this no longer happened, I could then go to the installation process, which worked flawlessly and there hasn't been a problem since. Since this was a shared printer, this problem simultaneously happened on 3 systems, all of which were upgraded to XP SP3. All the systems at one time independently had another HP printer attached to them (but different model printers on each). The problem did not exist on any system while under SP2.
All I can say is "good luck". Other than these painful steps that I used, I have not been able to find a clean solution to this problem.