Try the "Windows VC10-4" from Strato. I only had good experiences with the hoster. On 2vCPU and 4GB RAM i can host 6 Pluto/Tekno servers comfortably. And its hosted in the EU for 8€ a month but look out for sales.
Concering your Performance Problem with Linux, I had a dedicated Server on Hetzner and tried to run MW3 servers there. I tried it with Windows and different Linux distros, always had the same problem you are facing, poor performance and lags.
I bet it has something to do with the firewalls leading to your game server and back to the client. Just try to change your hoster, rent a small VPS just for a test run.
You may also try to contact your current hoster and ask him about the performance problems you are experiencing.