The only problem with NAT gateways is that they are single-AZ. So if you're setting up multi-AZ in a VPC, you need one per AZ and you need the routing to be AZ specific.

If the NAT gateway was a service, then it could be multi-AZ transparent to the VPC.