As Journeyman hinted, you'll need a copy of Windows Server running Terminal Services to support multiple concurrent users. Windows Server also has built-in support for hosting a VPN ("Routing and Remote Access"). Also, setting up a VPN is a good idea, but by no means is it absolutely necessary to do what you want to do.
EDIT: I just thought of another possible solution for Windows. If you own multiple Windows licenses, you can set up a VMware/VirtualBox/VirtualPC virtual machine for each user. Use Bridged Networking for each VM to make sure it's on the same LAN as the server. Then each user can VPN into your network and use Remote Desktop or VNC to connect to their own VM. The main drawback to using this solution instead of Windows Server is that you'll have to invest a little more in hardware (more RAM, more/faster disks, and possibly a faster CPU) to handle the extra overhead of running several complete Windows instances on one machine and balance out the resource contention.
If you're open to setting up a Linux server, you can configure remote X sessions to allow your users to run applications on the main server, but have the apps displayed on the remote clients. They could all use SSH tunneling to login securely forward the X sessions to their workstations (possibly eliminating the need for a separate VPN, depending on the server's network setup). Unless you have a Windows-specific application that won't run under WINE, this might do what you need, and the client workstations wouldn't have to be very fast.
Of course, if all you need to run are command-line applications in a terminal, you don't even have to mess around with X, since you can just set up a relatively minimal Linux server and let everyone SSH into it.