Something I've never tried before, but is it possible to reinstall windows without losing all the info on the PC. I've got the XP installation disk.
Hold your horses, it shouldn't come to that...
Do they come back, bigger, if you do the following?
Display Properties, Appearance tab, Effects button, check "Use large icons", OK, OK?
If that works, do that again, but uncheck the box.
Alternatively, Microsoft's TweakUI
PowerToy has a "Restore Icons" function under "Repair".