Its likely that you have a hidden partition on your hdd that has these files as part of a ghost image, if you dont have the cd downloading and installing the latest service pack can often fix these problems, however installing service packs can also be a little bit risky.
So first i would tryhttp://www.kellys-korner-xp.com/xp_tweaks.htm
number 141 - help chm fixer / repair
then i would try to borrow a cd from a friend, you will need to get one thats the same version (xp home or xp pro)
Normally you can purchase the cd media from the company (HP, Dell etc) you can try giving them a call
Then i would try installing service pack 3 for winxp. (but remember even though service packs should just work they sometimes dont, and your windows can end up unusable)
If it is a really problematic issue you can use the system recovery option, but this usually wipes all the data on your hdd and puts a new fresh copy back on, which will be missing your emails, pics apps and others, so you would have to backup any data you wanted to keep and reinstall everything.
The problem with the emoticons is a lot of them are adware or worse, and i would say that during the cleanup of your system the emoticons got removed.