73 is about the correct number for Windows XP SP2 fresh install / unpatched system
There are three particular updates that cause problems on previously unpatched SP2 systems as you have described
1) Patch for Windows Installer 3.1 must be installed for Automatic Updates to work
2) Windows Genuine Advantage - this opens up a sometimes unnoticed window behind IE when you are installing from Windows Updates and must be installed before updates go any further
3) Lastest version of Microsoft Update
Once you have all three of the above, MS Updates should work pretty much OK