Improve terminal services performance

Well with all the info you gave, here is what you can do.

Max out RAM on the servers, max out the CPUs on the servers. Heck, replace all of your servers with the latest ones seeing how you don't have a budget limit or a current setup. Run 1gig ethernet to all of your nodes, make sure your routers/switches are configured properly and setup in subnets for improved data flow.