BarTender: Still think pfSense is the best option especially if you have a Virtualised environment with spare capacity. Just dedicate a network cards to routing out to the internet, and since it sits on your ESX server / SAN, if that blows up you're dead in the water anyway. So no need to purchase new hardware.
Come on Laurence... Pull out the geek card and make it happen :)
What works for Geeks doesn't necessarily work for a business that requires support and has no in house tech capability!
But it's worth thinking about I guess since they are about to a virtualised environment with all new kit.