Problem: a HP desktop PC suddenly and consistently takes a very long time to boot. The HP invent logo stays for about 30 seconds when the machine is turned on (it should only flash briefly). Furthermore, the during Windows XP boot sequence the screen is blanked and stays black for more than a minute before the login prompt is displayed. Supplementary info: According to Bootvis, the boot process takes 130+ seconds. Moreover, in Bootvis CPU activity trace, CPU load is reported 100% during the black screen phase (with no disk activity). The same delays also occur when starting Windows in safe mode.
Solution: in this particular case, it was an external USB hard disk that somehow got stuck. Turning off the disk and turning it back again fixed both delays (HP invent logo and black screen), bringing boot to normal speed. Lesson learned: always first detach USB devices when troubleshooting this kind of a problem.