I am using Microsoft Dynamics NAV 2009's Role-Tailored Client (RTC), which utilizes a 3-tier architecture. The middle tier, which Microsoft calls the service tier, is a non-cluster-aware application that runs as a Windows service. I've identified through another question that I should pursue running a clustered hypervisor with a virtual machine running the NAV Service Tier.
Unfortunately, the NAV Service Tier has a recommended maximum user capacity of 50-60 users. With over 100 concurrent users, I will need some mechanism to "load balance" all of the sessions without having to visit each user's workstation and "hard-code" it to a specific server. Sessions will need to be sticky in that every request after the initial request will need to be routed to the same server.
How can I load balance a Windows service which is not IIS-based and meets the requirements I've outlined?
I think Windows Network Load Balancing (NLB) will work for you - it uses multicast to allow multiple servers to be accessed by the same IP address. The servers decide between themselves which one will handle a request. It can be configured to be sticky (session affinity). Be aware however, that it only offers redundancy in terms of whether a server is up or down - it can't decide which server in the cluster is under less load.
Most documentation out there will discuss IIS and NLB, but it works for RDP and other applications. I have had some issues using this over Dell PowerConnect switches in a high load scenario, and would be inclined to go for a more heavyweight load balancing solution, but I think for your purposes it is the best place to start. It's free with Windows Server.
How do the clients "find" the middle tier? Is round robin DNS an option for you?