Well, not much that can be done about caching proxies. Regarding DNS, have you been able to look at whether the IP's from failed requests show up on the new IP shortly after? I.E perhaps browser-pinning from open sessions?