Internet Access Restrictions

I recently sow the Firewall-1(firewall program)and i guess it could help uwith at least some of the requirements u neeed.Altough I am not sure if u can accomplish what u want with it,it would probably help u if u take a look at their homepage at http://www.checkpoint.com/ ,in my opinion it could make ur task alot easier.I assume all this because i sow a unique feature in supporting NAT&VPN,besides other stuff,therefore u will be able to put the www server behind the firewall,thus enabling u to use some small programm that would tell the firewall if allow or not acces to a specific user,acordingly to the policy of ur company.
I am not sure 100% that what i say here it's viable or not,because i had to read lot af documentation till i'll be sure to completly know all abut the Firewall-1,but u can see by urself if could work or not.
I don't know if this would really help u,but i don't see another way to do what u wish ATM.

If your company has a terms of use policy, the HR department should periodically send a paper copy of it to each employee and require it returned with a signature. If you have employees who refuse to sign, it is a corporate issue, not an IS issue.

You can block those employees easily in Proxy by denying access to their logins.

Putting up a screen every time someone loads a browser will only cause hostility, reduce morale, and get IS laughed at.

Think about it...