Users will click anything they find 'interesting', can't change that part up front. However, after those users get infected with whatever virii/worm/botnet client came along, you could detect it [1] and place them into a quarantaine vlan routing all traffic to an information page stating they have done something stupid and educate them how to clean-up and avoiding it from happening in the future again.
This will stop the abuse almost instantly (if the detection and vlan move is done automatically), and it will educate users afterwards by learning from their msitakes. Most users appreciate such kind of warnings from their own ISP (afraid of loosing documents by a virus) and are willing to clean-up. You could charge fees when users need clean-up assistance.
[1] Projects like ShadowServer.org scan all kinds of botnets and (after a sign-up) send out notifications to your abuse-desk when they find infected hosts at your IP subnets. You could also setup your own Snort IDS with the detection rules from EmergingThreats.net.
With kind regards,
Michiel Klaver
IT Professional