Si tu proveedor de vps ya incluye windows, no deberias tener problemas legales, y si no lo incluye, entonces si, tendrias problemas, yo conozco 2 soluciones,
1. Amazon EC2 .- rentas los servidores por hora, con el software incluido, puede ser puro windows y usar las versiones express del sql para que salga mas economico, sin embargo, te recomiendo que te des una vuelta y veraz que los precios son muy buenos.
2. Puedes inscribirte en el programa de microsoft BizSpark, para empresas tecnologicas emprendedoras, te regalan licencias de windows, office, windows servers, etc, buscale asi y ve los requisitos...