That doesn't sound like an Icon Cache problem to me...
opening something like Mozilla Firefox, I have to right click, open, and it says 'Choose the program you want to use to open this file'.
I do not believe this is conducive to an Icon Cache issue.
All the Icon cache does is display the icon, it has nothing to do with opening the actual application.
If this is happening on multiple applications, you have a bigger issue.
Your applications are losing file associations.
I would tell you to start here... Default File Type Associations - Restore