i used to use Server4you.com and it was dedicated server tbh, but i was using this one http://www.server4you.com/dedicated-server/ecoserver/ Large Option , you have to add i think 15 $ to use windows server, but that machine can handle so many MCs. Now i was using VPS on ovh.org "VPS cloud 2" and it was good, 10-14 mcs and much cheaper.
