A client of mine had this exact problem. Here's how we tackled the solution:
Installed an IPCop box with a built-in Squid proxy and also installed the URLFilter add on. All traffic now flows through the IPCop box.
Hard coded everyone's IP address to their telephone extension for the simple fact that it made it WAY easier to identify the offenders. We also changed all of the DNS server settings to point to OpenDNS. (Further filtering options are possible with OpenDNS but it turned out they were not required after all.)
Removed (and banned) the use of all public IM clients such as Yahoo Messenger, MSN, AOL, ICQ, etc., etc. Instead we installed a secure company-only XMPP server called SecuredIM so that all IM traffic would be logged and would be guaranteed to be company-to-company communications only.
SecuredIM also has the unique ability to take screenshots of desktops every XX minutes. If an employee was suspected of goofing off (based on IPCop logs) a picture was worth 1,000 words. Select screenshots could be archived and emailed for later review (or diciplinary action).
We blocked Facebook, Myspace, Hulu, and two or three other major abuses via the URLFilter on the IPCop box.
Manual review (and more sites blocked if necessary) for about a week.
Opened up "free/unblocked" surfing during the lunch hour (12:00 pm-1:00 pm).
By the end of the week the company was a total transformation. Productivity increased dramatically and nobody so much as complained.
As with any company, there's always the 1-2 rebels out there who think it's a "game".
When nytimes.com
was blocked they went to another news site. When that was blocked they picked yet another. Others stopped surfing and took up hobbies such as Solitaire and Minesweeper, but the SecuredIM screenshots caught that (IPCop could not obviously).
Within two weeks (and a couple of employer/employee discussions including disciplinary action for stubborn individuals) everything was running smoothly and has been running smoothly for almost two years.
URLS:
http://www.ipcop.com
http://www.securedim.com
http://www.opendns.org
SIDE NOTE:
As a funny side story. About a year later, an electrical problem in the building caused the power supply on the IPCop box to go out and it was 2-3 days before a new IPCop box could be put in place.
We found that it took less than 48 hours for the employees to go back to their old/original surfing habits and productivity to drop.
It was quite the social experiment. :-)