Unfortunately, mixing and matching ends up really complicating things especially with security in mind. Many people run within a VPC and bridging to another private network is, well, I don't really want to think about it at this time.

We've found OpenVPN to be our friend here: create an overlay network that doesn't really care if nodes are bare metal or "cloud".

I thought about that too, but as far as I see with OpenVPN you have the single OpenVPN server as single point of failure and all the traffic goes through the server, which quickly becomes a chokepoint. If I needed this again, I'd try out tinc first. It does not appear to have the single point of failure issue.

We have multiple standby servers to prevent the SPOF issue.

One problem we HAVE seen is a reduction in maximum bandwidth. Since we're CPU limited, however, it hasn't really been an issue.

That's the thing - it is much easier nowadays. Kubernetes requires your containers to run on flat shared networking namespace, so your new machine joins that network. It is like running within VPC. Software like Rancher makes the process of adding new server a matter of executing a one liner on server.