Issue resolved! Thanks to all for the help. This was a hardware firewall issue with the web host, even after they were disabled by us.
As confirmed by 1&1's server team, the hardware firewalls were correctly configured, but they were incorrectly intercepting valid traffic about 25% of the time.
We have configured iptables instead and shutdown the hardware firewalls entirely. 100% availability now.