Mouse cursor jumps around when using RDP

We have over 350 users complaining that their mouse cursor keeps jumping around when typing. It seems like it's happening when the protocol is starved for bandwith, but I'm not quite sure yet.

If it only was the cursor moving it would be fine – problem is that it also moves the focus so that they are suddenly writing text in a different place in the document without noticing too late (old people, they stare at their keyboards).

Most users have laptops, and I've also suspected the trackpad not sensing typing (and thus not deactivating one-touch click on the pad), but I got a report today that a desktop user experienced the same.

What could cause this? Is there any way to tune RDP so that it won't happen? I'm lost..

EDIT:

Some more background info on how we have RDP set up:

• RDP encryption level is set down to "Client Compatible" via GPO in order to support older CE thin clients
• RDP compression is set to "Balances memory and network bandwidth". Same reason as above, to support older RDP clients
• All RDP shortcuts for the users are configured to only use visual styles + persistent bitmap caching. We have tested without visual styles, the mouse still jumps around
• All RDS servers are limited to 16bpp colors, desktop composition and backgrounds are not allowed
• Our MPLS provider has QoS rules in place to keep RDP above Best-Effort (see EDIT2)

EDIT2:

I've inspected the MPLS providers QoS setup, and something feels wrong here (pastebin).. internal RFC1918 traffic is being prioritized in the class below RDP, but with the same drop probability. I'm thinking that this should be in a class further down the list, with a higher drop probability.

I've talked to several employees today, and it seems like this problem is reproduceable if they fire up a ton of domain-joined computers at once (group policies, WSUS updates and so on).

MPLS provider has been approached, and I'm waiting for a free technician to change the QoS settings to see if this helps. I'm going to dump all traffic but RDP on a single site into Best-Effort and see if it helps.

UPDATE 19.07.2013
Still not solved. Discovered that nearly every laptop is missing the touchpad driver, so the touchpad is not being deactivated while the user types. Baaaad.
In addition it also happens with desktop PCs, and on any kind of PC with a bandwidth constrained pipe. I've asked a new question on Network Engineering: https://networkengineering.stackexchange.com/questions/2427/qos-woes-managed-ip-vpn