I never really understood the concept some people have, such as you and your bosses, that staff are mere fodder for the machine. I'll explain why:
Firstly, it's your staff that enabled your company to exist and prosper in the first place, so this thing about desktops etc being the propert of the company is rather disingenuous.
Secondly, blanket blocking policies only demonstrates a draconian and rather myopic view of user policies. They also don't work when appplied to topics such as IM.
Third, any company that treats staff with such disdain can expect low staff loyalty and/or motivation. Cut your people some slack and you may be surprised at what you get back in terms of positive employment relations and productivity.
Overall though I feel rather sorry for you. Must be a wonderful atmospehere in your office. Not.