You're correct -- it's a tricky proposition.
I don't know if my configuration is brilliant or ridiculous, but I decided to avoid the need for the network to reconfigure itself by providing each availability zone with its own hardware... here's what I use:
In each AZ, I have a VPN instance, so for two regions, 3 AZ each, that's 6 total. They are t2-class machines, so very cost effective with nice performance. Each of these has a tunnel to all of the units in the remote region, so each of the 3 machines has 3 tunnels to the 3 AZs in the remote region.
The VPC routing is static -- all traffic for the far end IP blocks in each AZ routes to the tunnel server in the local AZ, which encrypts and encapsulates it, and sends it on its way. Each tunnel server has static routes to the subnets in the remote AZs, terminating at the correct VPN node on the far side for the destination availability zone. (The subnets in each AZ are a contiguous /21 netblock, so it's only one route to each).
On the far side, the reverse is true.
So loss of a VPN node results only in isolation of the machines in the availability zone where that node lives, from all zones in the remote region, so the other availability zones in the same region as the failure are not dependent on any kind of failover mechanism -- they aren't impacted.
The actual loss of everything in an entire availability zone would have no impact on any other zone's VPN connectivity with unaffected zones with this setup.
The VPN machines actually have two ways to reach each of their peers; the first is the "normal" route, over the Internet to the peer's elastic IP, and the other is through a backup route, where the VPN servers all connect hub and spoke to a concentrator not in the AWS network -- the theory, there, being that the tunnel might survive a partial loss of direct Internet routability, the traffic taking a different backbone to the alternate hub site and being relayed to the peer, allowing them to pass traffic over a slower and more latent backup path, without a loss of tunnel connectivity in the event of a loss of Internet connectivity. Since primary and alternate paths terminate in the same instance on each end, and the backup "hub" is not tracking flows, brief periods of asymmetric tunnel traffic routing during a flap don't cause any problematic issue.
A failure of a VPN node does have to be addressed in order to restore connectivity to the impacted zone. Or changes to the route tables.