That's an age old "issue" as it only installs the icons for the user profile it was installed on.
To make it accessible for all users copy the shortcut to the All Users Desktop, and All Users Start Menu, or just manually create a shortcut pointing to it in those places.
If everyone on your system is going to be using it I'd recommend everyone read the official documentation:
What you say is very interesting because on my old comp running XP my wife and I have used it with no problems.I just installed it like any other program and it was on both our desktops.
Perhaps you were using a different flavour of XP, or it had been configured with different defaults.
Allot of people share the same profile though. Although it would be advisable for Piriform to at least put the shortcuts in the All Users areas as this has been a never ending user issue and user request for several years now. So long as they'd keep each users individual CCleaner settings in their own registry area, or start using the Users own unique Application Data folder for storing individual settings if someone chooses to use the .INI instead.
My old computer came with XP Home preinstalled [Compaq] and it was our first computer so I didn't mess about changing any settings. My wife and I were both administrators, whether that would have anything to do with any thing I don't know.
When we changed to this new computer we just thought that we would download the program again and carry on as before. It wasn't till Advari mentioned it that we knew that everybody on the computer couldn't use it. Crazy.
I wouldn't mind but we only use it to clean up after surfing the internet.