Among many of my responsibilities, I am in charge of directing the Antivirus and Electronic Information Security divisions of my organization. We have over 15,000 desktops and also offer remote access to our employees and various other outside agencies.
Using GroupShield is a good call. I don't have the problem of users accessing outside email accounts as it is literally illegal for employees to do so from our network and they risk jail time as a result.
I agree with your friend who blocks other mail at the firewall. What you may want to do (it all depends on your environment if you can) is block outbound TCP port 110 at your firewall. This will disable the ability of anyone to access POP3 mail at any other server that is outside of your firewalled network. If you have key people that need access, you can open the port for them at the firewall and still deny access to everyone else. If you do open that port for a select group of users, you must instruct them on general virus avoidance and make sure that their machines are up-to-date on the DAT files every day.
Regardless of if you block the port or not, anyone using your organization's (or company's) resources in a non-approved manner should be subject to disciplinary measures. Getting a virus that causes downtime and data loss is very expensive when you take into account lost productivity, administration time, data loss, etc. It is akin to having someone with a company car drive it through your front door. It is unapproved usage of company resources.
If you need help on drafting up a generic Terms of Usage for your electronic assets, surf around on your favorite college's website. They tend to have the best verbage to perform some CYA as well as make the verbage non-technology specific...e.g. copyrighted works vs. MP3 or pirated software.
Last but not least, kick their ass for making you do extra work.