Let me guess.
You deleted the program as in you went into program files, and shift-deleted it yes?
Reinstall it, and remove it from add/remove programs in control panel, the proper way. I assume it's hooked the download trigger in IE, which is now trying to start a program which doesn't exist.
As for windows update, you're no doubt using a pirate copy of windows XP professional with a copied volume liscensing (aka. corperate) key. There were only about 5 of those ever leaked (since they cost the companies which purchase them one HELL of a lot of money) and MS have blacklisted them.
Well, not exactly blacklisted the key - but they have blacklisted the product ID codes the keys generate (look on the first page of the System control panel applet to see your Product ID code).