I finally have response from Linode guys, they decided to raise limits for pool significantly. Unfortunately it need balancer restart to take effect, so expect short outage.
This should solve stale rate and RPC errors (but today's errors were caused by database error, which is already solved).
EDIT: Great, looks like that annoying packet loss is solved! (0% in 2000 requests)
Just want to say thank you Slush, the connection stability and overall responsiveness has been greatly increased

There are still some issues with idle miners, but it is a lot better then before.