Well the only thing I can remember for sure that I did any different when I got this problem, is that I didnt set it to Automatic Updates when I installed XP... is that I updated manuelly through Microsofts Webpage. Not that I see how that could be the cause of it all.
And if you did a clean installation of it all and restarted after each Update, I dont see for sure how Not restarting after each update is the cause either.
Let me just tell you how I installed it when it worked out for me then, for what its worth:
1. Installed Xp
2. Installed Motherboard Drivers
3. Installed Graphic Drivers
4. Updates for XP this time set to Automatic Updates and I know for sure I restarted after each update this time
5. Installed Whatever program I use, AVG, ZoneAlarm, ICQ etc etc
Thats all I can do for you man, sorry I guess its pretty useless information =/
anyway I hope you get it to work next time, if you decide to try another re-installation, I know how annoying it is. Good Luck.