Acho que deve ser um firewall ... pode muito bem ser o firewall do Windows.
Tente desativá-lo completamente temporariamente (se estiver satisfeito!) para testar. Execute o seguinte a partir de um prompt cmd elevado (executado como administrador):
netsh a s a state off
Se isso é uma solução que permite que você ssh em então você encontrou o problema, então ligue o firewall novamente (novamente a partir do prompt cmd elevado):
netsh a s a state on
Em seguida, você pode tentar abrir a porta 22 de entrada usando o seguinte (elevado novamente):
netsh a f a r n="Open Port 22" d=in a=allow prot=TCP localp=22
Isso é para todos os perfis.
Se a desativação do firewall do Windows não permitir que você receba o ssh, então ainda ligue o firewall (obviamente!). Mas pode ser um firewall ainda mais avançado, como no gateway do seu provedor de VPS.