Ended up being a router on my customer's edge was completely saturated/overloaded, adding 400ms+ of latency.. So looks like something where the complete request couldn't be sent quick enough. We have reproduced this same behavior adding 400ms of latency with tcpproxy.
Sometimes it's the most obvious explanation, I guess...