Our biggest struggle has actually been with outdated software. 16bit software just won't run on Win8 (64bit - can be enabled on 32bit, but that's just another wall waiting to be hit), and while our admin would be comfortable with installing a VM to keep these going, we're just biting the bullet and converting legacy files to formats used by more modern software, finding alternatives for those applications that we do still actively use, and keeping two machines around for everything else; one running with a VNC, and the other in storage 'just in case'.
Run VirtualBox on a machine and setup the appropriate guest OS to run your software. Enable remote display in VirtualBox for your newly created guest OS. Now anyone can connect using RDP or VPN - whichever you decide to host. I recommend RDP because the Windows clients will already have client software installed.
This is easier than setting up VM software on every computer. It also removes any restrictions governing which computer you can use to host the VM. And finally, it makes creating backups of your guest OS / application much easier as you just backup the VM image. The ability to take snapshots of the guest OS is also very useful.
Of course, other VM servers would also work. My experience is with VirtualBox and, despite being free, works suprisingly well in this sort of situation.