Losing a priviledge that you have been given is always a problem. Employees tend to view their email and Internet access as a normal part of the job and not as a priviledge.

First, the email side of it ...

Personally, I'm limiting my personal email use at work to the minimum, simply because I have been changing companies, so my work email address is not a good address to reach me.

I think Lostit44 is on one track that can help, user education. However, you will need to consider a set of follow-up steps, because some users will not be willing to listen. Difficult as it is, after a period of education, users who continue to receive non-work related emails and attachments should be talked to directly. However, this means some form of email monitoring, which is a privacy issue. Your company would need to make clear beforehand that all email can be monitored. Unfortunately, that's what you will need to do with some users.

Also, you would probably want to restrict access to the web-based email providers such as Hotmail (after all, would you trust Microsoft to have an up-to-date virusscanner checking attachments?) or Yahoo. My previous employer did that, it was a pain at first, but you get used to it and the number of viruses received diminished quite a bit.

Next, the Internet surfing ...

I think that the Web can be a great tool to support work activities. However, a lot of time can also be wasted on it. One thing you can consider is site filtering to deny access to porn, gambling and other "sinful" sites.
(Wired just ran an article on that: Filters Block 'Sinful Six'
)

Although employees might grumble, they will be happier with access in a limited way based on a rational set of restrictions than no access at all.

You're better off not creating separate users with web access. This would create tension and jalousy in the company. It can also lead to abuse as people try to use other people's accounts or computers just to be able to access things.

Anyway, to resume all this:

Educate them and consider the use of some selective site blocking. And have management remind them that company time is not made for personal web surfing.

Cheers,

BrainStop

PS = And if it doesn't work, you can always start to monitor all traffic that passes through your proxy and firewall and then have a chat with users who abuse resources ....