That's the right approach. Get a managed dedicated server and install virtualization software on top of it. It's the most cost-effective way. You'll then be able to create as many Windows VPS instances as the resources permit (CPU, RAM, disk). Be sure to ask the provider for their IP allocation policy (shouldn't be a problem but it's better to ask ahead of time). Also, do discuss your goal with them prior to signing up.
You'll have to figure out how much resources the server will need (memory, hard drive, CPU, and bandwidth).