After tackling this issue for multiple days, I've finally found a way to fix keyboard/mouse lag issues in RDP ICA sessions. Turns out, in Windows Vista (ick) Microsoft introduced an auto-tuning feature that can be enabled to speed up the TDP connection.

These two lines need to be run in an administrative command prompt:

netsh interface tcp set global autotuninglevel=highlyrestricted
netsh interface tcp set global rss=disabled

If that doesn't take the cake, I generally blame the Superfetch service which is supposed to "Maintain and improve system performance over time" according to its description in services.msc but it generally does the opposite for RDP sessions considering what the does is execute svchost.exe -k LocalSystemNetworkRestricted.