I use NFOservers. They allow you to use Windows natively (though they charge you slightly more) so you don't need to use Wine or some other bullstuff.
2core/2GB will cost you $17.54/mo if you buy in 3 month increments, I would also recommend going with Windows Server 2008 since it has less bloat and runs better with lower specs.