I've personally never botted ever at all, let alone on a vps but I do use vps's for everyday uses on the net. If you're wanting to run it on a windows vps (which will cost more than a linux due to windows licensing fee and most don't offer unmetered bandwidth) than I'd suggest checking out santrex.net or turbovps.com.
I'd recommend though if you're going to be botting on a vps that you do take the time to learn how to set it up on a linux vps as it will save you more than half your costs in the long-run.