This was one of the reasons we handled server deployments ourselves for our startup. The cloud version of our app runs in production on AWS in a VPC so all outbound traffic is NATed through a single public IP. With reserved instances it costs about $22/mo for the NAT gateway and setup was pretty straightforward.
I've considered doing this myself so I'm curious: are you getting good network performance through the NAT gateway? What instance type are you using?
At the moment we're using an m1.small for the NAT itself though if you have perf issues you can bump that up as well. I would guess a c1.medium would be more appropriate though as I said we haven't had any issues so haven't considered changing anything yet.
Here's a speed test through from a m1.small through the NAT (27.5 MB/s):
$ curl -o /dev/null http://speedtest.wdc01.softlayer.com/downloads/test500.zip
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 500M 100 500M 0 0 27.5M 0 0:00:18 0:00:18 --:--:-- 29.2M
Here's a speed test from a m1.small vanilla EC2 instance outside the NAT (38.2 MB/s): $ curl -o /dev/null http://speedtest.wdc01.softlayer.com/downloads/test500.zip
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 500M 100 500M 0 0 38.2M 0 0:00:13 0:00:13 --:--:-- 34.1Mhttp://aws.typepad.com/aws/2013/03/amazon-ec2-update-virtual...
https://addons.heroku.com/proximo does what's needed, but at a serious price for high volume.