I think you are definitely right that IPv6 would mitigate, but I think that the real way to avoid this issue is for the kernel to make the tradeoff for you - it

I think you are definitely right that IPv6 would mitigate, but I think that the real way to avoid this issue is for the kernel to make the tradeoff for you - it's so cheap to do an arp ping, you might as well on maybe every 100th packet or so. Or similar: timing out and clearing the arp entries more frequently. As for other cloud providers, I'd be really interested to hear from Digital Ocean, Rackspace, and Google!