Hi kd5.
I've just tried to duplicate your problem.
I've tried a shortcut pinned to the "Classic" style menu and CCleaner opened from that pinned shortcut within a few seconds.

I've actually had my CCleaner shortcut pinned to the normal XP style start menu for as long as I can remember, and I've never had a problem with a delayed start.

This doesn't mean that anyone disbelieves that you have this problem, just that it makes it difficult to pin down as I feel pretty confident it may not be a CCleaner bug. This is the first time I've encountered this particular issue, and we usually get folk jumping straight into topics if they have the same problem, but none so far.
What the other guys are trying to find out is where the problem lies. Is it with the shortcut, or is it with the exe file, or indeed something else. This is why Marmite asked you to try launching CCleaner directly from its exe file in the program files folder.
We don't expect you to ask your customers to do that, it's just an exercise in elimination.
If it launches OK from there, then that eliminates the exe file being the problem.
What Alan was trying to explain is the fact that a user produced INI file, winapp2,ini, containing a lot of entries suggested and supplied by CCleaner users, has been the cause of CCleaner slow downs.
Alan was suggesting removing all the entries alluding to software you don't have installed, which isn't cobbling CCleaner, as the normal INI used by CCleaner is embedded in the exe file.
As the winapp2.ini isn't installed by default, you probably don't have it, but I would still check the CCleaner folder to make sure.
All that out of the way, it can only be a case of trial and error to find the cause of your start up hang.
Do you install CCleaner on all of your machines from the same installer, or do you download new installers for each one?
Have you tried a complete reinstall of CCleaner with new shortcuts?
Have you tried launching CCleaner with your security software disabled? While disconnected from the Internet of course.
Can you launch CCleaner either directly or from it's pinned shortcut in "safe mode". If so, it eliminates CCleaner and the shortcut and would suggest something loading with Windows is causing a conflict of some sort.
There has to be some common denominator with your XP machines reacting in some way.
Is there any difference between the CCleaner shorcut and the others you have pinned?
What I mean is you can have an exe file pinned to the start menu as opposed to a shortcut.
Example:
My CCleaner pin is a shortcut:

My Process Explorer pin appears to be the ex file itself:

Just a few thoughts to try narrow down the possible causes of this issue.