The IT or PC support manager probably has the most to lose if there is a problem.
So, ultimate responsability rests in their department. Along with top management.
There must be strong support from upper management for any policy to function. This includes a willingness to expend funds to clean up any open issues.
After that, it comes down to an issue of policing the policy. Again, this is easier if users and managers don't have to play 20 questions, and spend 3 days justifying why they need a piece of software.
As draconion as it sounds, the best thing to do may be to have a secure cabinet with a box or folder for each PC that contains the original copy of all installed software and registration certificates. If there are instances where the user needs regular access to the CD, you can legally make a back-up copy for their use.