i think method will work but method 4 is a little extreme especially when you have to pay extra to handle things.
To add to those already good suggestions, here is what I would do (to make my life easy) :
Leave the cdrom in the system but disable it. either through hardware like disabling the secondary ide or through computer management (under removable storage) in each PC.
Or you can use group policy. Under group policy, you can make all CDROM as D drive and then disable access to D drive. OR you can specify to disallow installation of program from removable drives under "windows installer" group policy. But then this does not mean they can't copy the installation to HDD and then install from there.
I guess it all depends on how extreme you want to implement the policies. If the network is small, my preference would be to limit the cdrom access only to administrators. That way, if the users really need to use the cdrom, they just give you a call and you use "run as..." to give temporary access until the logoff.
If you have large clients, the best method is to use group policy but as you know group policy takes time. But then really have few methods to implement this. For example, you can allow only certain person to use cdrom (someone you can trust or manager). This cdrom is shared among a few person maybe among same deparment. So, blame it on this person if you find that department is playing games.
Hope it helps...