My first and foremost suggestion is to get a legitimate copy of Windows XP. Secondly, see if you have a file named scsi1hlp.vxd (do a search for it). If so, change it's name to scsi1hlp.vxd.old and reboot. See if that helps. Probably not, but it's worth a shot.
What doesnt make sense here is that you said that you have the messenger service blocked at your firewall. If thats the case it theoretically shouldnt be able to get thru to you. the message you are showing is in line with the link bobrek gave...but they use the messenger service to popup. Which you have blocked...how did you block it? Did you use these instructions? or possibly you blocked the MSN messenger ports instead of the XP messenger. double check to insure that you actually disabled the XP messenger service...and see if it still happens.
ok, the HD was a problem before, but you installed a new CDROM? was that a typo? and you meant you installed a new HD? another cause I have seen, was when the CMOS settings were not compatible with the actual hardware installed...is this a store bought computer? and have you messed with any settings previous to this problem occuring? I know it is unlikely, but I thought we would at least cover all possibilities...
funny thing is, my computer here at work just started doing the same thing. I'm willing to bet it is a driver problem. how long ago did it start doing this? maybe you should try a system restore..
When you do windows update, if you read the terms, it specificly says that it will NOT check the serial number... etc. If the automatic windows update isn't working, just do it manually. Website is WindowsUpdate.microsoft.com. Some of the updates won't work properly with with bootleg versions, but since you have legit copy all should work fine.
It lies... I have a friend that was using a cracked version of XP pro, and when he tried to do the update, it came back and told him his copy did not have a valid serial. Lesson: NEVER trust what Microsoft claims.