OHV/Kimsufi dedicated boxes can run windows no problem as they are physical hardware. You either have to get a licence through them, or add your own key in their manager before you install. I've done it with my own key after a couple of attempts to get one that worked with the images they have available.
To be honest though you are better off with a linux VM, i run my server on one in the UK and it costs me £8 a month for 2gb ram with an extra 512mb burst, 50gb disk and 1.25Tb of transfer. Plenty of offer's to be had out there.