Route table and subnet association

In a very similar situation as the one described in the question I was able to solve it by adding the proxy configuration to /etc/yum.conf.

Like this:

echo "proxy=http://my.proxy.internal:3128/" >> /etc/yum.conf

This route table seems silly

Yes, in your interpretation of it... but your interpretation isn't correct. The route table entries in VPC do not actually have an order.

The most specific route is always selected.

Each route in a table specifies a destination CIDR and a target (for example, traffic destined for the external corporate network 172.16.0.0/12 is targeted for the virtual private gateway). We use the most specific route that matches the traffic to determine how to route the traffic.

http://docs.aws.amazon.com/AmazonVPC/latest/UserGuide/VPC_Route_Tables.html

However, your configuration still doesn't work if the NAT Gateway is actually located on a subnet that uses this route table. The NAT Gateway must be on a subnet whose route table doesn't have any routes pointing back to the NAT Gateway -- otherwise, that's a routing loop. Towards the Internet, the NAT Gateway uses the VPC route table of the subnet to which it is actually attached in order to access the Internet Gateway... so it has to be on a different subnet from the one with the instances that are going to use it, because this /32 route can't be placed where it will impact the outbound traffic from the NAT Gateway.

This is counterintuitive to people who don't realize that the VPC network is not a conventional Ethernet network with routers. The entire network is software-defined, not physical, so there is no performance penalty when traffic crosses subnet boudaries within an availability zone, such as is the case with an EC2 instance on one subnet using a NAT Gateway (or NAT Instance) on a different subnet, or an Elastic Load Balancer on one subnet connecting to an EC2 instance on a different subnet. Indeed, traffic crossing from one subnet to another in these cases is the standard configuration, placing NAT Gateways and ELBs on public subnets (default route is IGW) and EC2 instances on private ones (default route is NAT device).

Note further that the configuration you're attempting will allow outbound, but never permit inbound connections (initiated from outside) from the A.B.C.D address to anything on this subnet, because the return route is asymmetric through the NAT gateway.