Amazon VPC unable to access internet from private subnet

In order for the 10.0.0.88 instance to access the Internet (or EC2) via the Internet Gateway (IGW), the instance either needs to have an associated Elastic IP Address or needs to be talking through a NAT instance (which has an Elastic IP Address).

To lock down an EC2 security group to allow traffic from the VPC instance, specify the allowed source as the Elastic IP Address from either the instance itself or the NAT instance, as discussed above (ex. 192.0.2.25/32).

Given your updated question you are presumably using the official Amazon Linux AMIs configured to run as NAT instances ('ami-vpc-nat') and setup according to NAT Instances? This is obviously not required, but provides a sound baseline to achieve the desired stability of course. Regarding your question:

Fortunately AWS has recently announced Elastic Network Interfaces in the Virtual Private Cloud, which allows you to Create a Low Budget High Availability Solution (please refer to the Elastic Network Interfaces user guide for details):

If one of your instances [...] fails, its network interface can be attached to a replacement or hot standby instance pre-configured for the same role in order to rapidly recover the service. For example, you can use an ENI as your primary or secondary network interface to a critical service such as a database instance or a NAT instance. If the instance fails, you (or more likely, the code running on your behalf) can attach the ENI to a hot standby instance. Because the interface maintains its private IP address, elastic IP address, and MAC address, network traffic will begin flowing to the standby instance as soon as you attach the ENI to the replacement instance. [...] [emphasis mine].

So you should be able to achieve your goal with a modest amount of automation code - depending on how much you value redundancy/resiliency you have two options:

• a hot-standby NAT instance (minimizes downtime)
• an on-demand NAT instance replacement (minimizes cost)
  • You could implement this scenario via an Auto Scaling Policy, that maintains your NAT instance scaling level at 1 by means of an appropriate Health Check
    Update: This wouldn't currently work as per sborsje's comment, thanks for the insight!