Do they need internet access for their jobs? If not then just block all access completely.
If they do then abuse of the internet should be treated as abuse of any other company resource and the people taken through the disciplinary procedures. There's not a lot else you can do. You could look into why they're abusing the net access; are they bored; would they slack off in other ways if they were denied the internet; are you really sure they're abusing it and not just taking normal breaks? People can't work for 8 hours flat out; we all need periodic breaks and if someone's using it for, say, 30min/day and achieving/exceeding all their goals, then I'd say they're using net access for downtime and overall benefitting the company.
For mail just run a corporate mail server. That won't give them access to the internet.