I had a similar issue, the difference being that I'm using only private addresses within the VPC subnets.
As Brian said, your limiting factor is AWS, so apologies if the following is a bit off-topic for this group...
The solution I used was to use ansible to automate a redundant pair of NAT instances in separate subnets based on the following guide:
http://aws.amazon.com/articles/2781451301784570. By setting the service's subnets to have a default gateway of the NAT instance in the respective AZ, you ensure all instances in the subnet advertise on the static NAT instance IP. It also allows for auto-scaling as the route is set at the subnet level and inherited by all instances.
This is a functional solution but does suffer from a number of drawbacks, e.g. not an instant failover if a NAT instance fails, your throughput is limited by the instance types for the NAT instances, etc.