Try the Checklists and Troubleshooters in these articles.
310064 - HOW TO: Troubleshoot Windows XP Problems During Installation When You Upgrade
I would imagine that if you are booting from a CD and choosing the Repair Windows option (and you are using the correct CD for your machine) it really shouldn't matter as to what updates are installed as the repair should use the files on the CD and bring you in at that Service Pack level.
If it was a problem, then either uninstalling SP3 or Slipstreaming SP3 into your current XP CD would circumvent it.
How to remove Windows XP Service Pack 3 from your computer
Slipstreaming Windows XP Service Pack 3 and Create Bootable CD
Autostreamer
Slipstream Service Pack 3 into Your Windows XP Installation CD
Windows 2000/XP/2003 SP Slipstreaming
Or use nLite to slipstream the SP onto the XP cd...
You will have logging from the failed setup that might offer some really relevant clues too.
834647 - "Service Pack installation did not complete" error message when you try to install a Windows 2000 service pack
243996 - How to Enable Verbose Logging in Windows 2000 GUI-Mode Setup
Windows Setup and Device Installation Logging
You can also review the Setupapi.log file, the Setupact.log file, and the Setuperr.log file (in the %windir% folder) to try to determine any problems.