Websurfing policies and safe practices

I manage IT for a small company (2 locations - 7 servers - 45 users).   When I came here a year ago the company was in midst of rapid growth, much computing infrastructure had been added with little precautions taken towards security.  There were resident viruses throughout the network - everyone in the organization was operating and websurfing with admin rights on their computers.
I have some training and experience in a broad spectrum of IT - I am no security or Information technology guru -
I get 2 newsletters dealing with the latest security issues, viruses, malware, patches etc.  They very effectively alarm me.
 I have established a policy of "If it's not business related, Don't do it on company computers".  I get users complaining every now and then that the policy is over heavy handed & I still have users periodically websurfing sites (No real surprise) that have no bearing on our business.  
I am making headway (all users are off admin accts and on limited rights user accts - AV is installed everywhere - ISA is firewalling in one location and a hardware firewall in place in the other - all external laptops connecting have a software firewall installed.
Every time (and there have been several) that I research the potential danger in users surfing to the wrong site, I come away alarmed.
I believe that ISA 2004 can effectively be set up with different url lists that would effectively allow complete management of Blacklisted and Whitelisted websites for different users or user groups.  This would then require all of our users to submit a request to have any website they need to visit added to the approved list.  
Here's my question - Is this overkill or overbearing?? - OR is it actualy good practice that is recommended and in limited or widespread use in the corporate world?  Ramifications and/or consequences??  All responses appreciated!  Thank You