Software

not sure if you tried all these

tothepc.com/archives/10-ways-to-access-blocked-gmail-at-office-school-work/

and then you can just block google altogether. Bing or yahoo will both work just fine for them.

garbage.

Build up an Untangle firewall box to put between the network and the uplink router. This will give you plenty of control of where your users go, and what they do.

You could then block all webmail, as a category, and block social networking while you are at it. Guaranteed to boost productivity, after the troops stop complaining about it.