"The hardest conundrum to crack is to balance security with end user requirements i.e. blocking personal email (gmail, yahoo, etc) and blocking all removable media."
Oh dear, an IT manager dinosaur. You guys are in trouble. Securing the perimeter is a hopelessly outdated model.
If you make your systems unpleasant to use people will work around your restrictions.
Accept that your network will be compromised and design everything with that scenario in mind.