If the policy was such a great policy, why not apply it to everyone instead of middle management and lower staff? Second, if the CEO came to you to ask why, it would seem inherently obvious that he was unaware of a policy that you implemented across the organization. Last, I would compare your checking of internet activity to that of HR picking through personnel files. Sure, the company has the right to blah, blah, blah. BUT, it is not the role of IT to monitor employee productivity. It is the responsibility of the individual manager to do so.
Your "security" answer is simply an excuse and there is not a system around that is 100% protected against all threats....except the PC that is sitting in the box, powered off.
Interestingly enough, I also run an IT Department and have built my career on fixing the crap that IT Managers such as yourself implemented before I came on board. I treat my end users and staff with respect and not like little children that need the heavy hand of IT to dictate where they can go on the internet. What else? Did you lock down the desktops so nobody can change their background?
One last question....Was your internet locked down too or were you above that?