best and most efficent way to prevent inappropriate use of the internet

i'm not familiar with your router, but if you can establish egress filters for outbound traffic from the client workstations, you pretty much nip this in the bud quickly.  setup a filtering proxy for web and make allowances for that one host.  and inform your employees in writing of the nature and severity in which violations will be dealt with.  if/when someone figures a way around it (ie, externalized web-based proxies, etc) - chop off their hands and feed their young to the toilet trolls....and take pictures.

the last part's an obvious joke - but seriously the best way to prevent this is to make it unaffordable to violate.

Yes, first you need an acceptable usage policy. Please view the policies here, as they are well written, and easy to make your own, with a simple search and Replace.
http://www.sans.org/resources/policies/  You'll want your users to read and sign an acceptable usage policy first. Then you'll need to police them "manually" until you get your defenses setup.

Snort will detect a ton of the policy abuses. WinXP and 2000 would make your job easier, as you could keep users from installing software on their own... but to remedy that, you can use the free ZoneAlarm, it has process detection, and could stop your users from installing software, and keep many hijackers at bay also. ZoneAlarm can block/pause a process, it prompts the user to approve, and you can set a password that they do not know, and that will keep them from approving "unapproved" software.

There is no All-in-One solution, security is a Process, not a Program. With your budget you could definatly get the job done. Also get control of ActiveX on IE, or move to Mozilla,
since it doesn't get spy-ware and it's pop-up blocker is very good. The program is free also: http://www.mozilla.org/

You've got your work cut out for you... get the policies signed by the employees, get the "un-work related" software off the PC's. Then get ZoneAlarm on the PC's. Each and every program that needs to act as a server, or access the internet will have to be approved by you, this is good, but slow. Also once you've entered the password to approve, you're logged in to ZA, if your done with the machine, you'll have to "logoff" ZA, so that your users can't just start approving software on their own.

Once you do get to XP, you can get rid of the ZA, as you can place your Users in the "Users" group, who can't install anything really. The "net send" is an effective tool, as is coming by thier desk with a signed acceptable usage policy and reminding them that you can see everything they do.

We need
a) internet radio blocked, instant messenging of all flavours blocked ( easier to police your users with Snort, then send them a "net send" message to tell them to cut that out)
b) access to inappropriate web sites blocked, ( a whitelist is an option, using a proxy is the easiest way to do this, or something like " Net Nanny")
c) spam removed frmo emails  (personal experience, Spam Assassin http://wiki.apache.org/spamassassin/UsingOnWindows)
d) some automated protection from spyware ( the pay version of ad-aware is great!... but the free mozilla browser is better)

You don't really have to set ZA up to really Firewall much if you don't want to, the pay version would allow you to set up some very nice rules... but I mention it here because of the process locking/blocking features, to keep your users in line. ZA can't be uninstalled with out that password you assign.

Again, it's not an easy thing to do. But if you have documentation and their signature, they have been informed, and SHOULD know better. The google toolbar is good to block pop-ups, but I don't think it will install on such old OS.
GL! (you'll need it)
-rich