I'm using minerd miners (no default stratum support) connected to a central stratum proxy. That stratum proxy connects to a headless linux VPS forwarding all traffic to whatever pool I choose. All I did was change the IP on the VPS to point to Middlecoin instead of Wafflepool and all of my rejects went away. So something else is going on, because my miner configurations haven't changed at all since I started mining LTC a year ago. I guess I was just having connection issues to just Wafflepool.
minerd=cpuminer? I ask because I use cpuminer and the executable is called minerd, and it has stratum.
Did you ran some network tests from your VPS to the pool servers? (ping traceroute etc.) Because it looks like your shares are "killed" by latency as they travel.