Configuring proxies

I have been having an issue with PHProxy and CGIProxy. My upstream provider had been receiving complaints about spam emails sent from my dedicated server. My host contacted me, and the techs worked out that people had been using the proxy on the server to log into email accounts and send out spam messages. My question is how can I configure them so people cannot use mail systems like Hotmail etc. I can always ban the sites...but there are so many. I still want people to be able to login to sites like MySpace, Facebook etc...how do other proxy sites do it without any issues?

Thanks.

Seb