If you are using vagrant, you probably-statistically are using git. Make sure you have its binary folder on your path, because that path contains 'ssh.exe'.
Now, modify C:\vagrant\vagrant\embedded\lib\ruby\gems\1.9.1\gems\vagrant-1.0.3\lib\vagrant\ssh.rb
to comment out the faulty Windows check and add a real SSH check:
if Util::Platform.windows?
if !Kernel.system("where ssh >NUL 2>&1") && !File.exists?("/usr/bin/ssh")
raise Errors::SSHUnavailableWindows, :host => ssh_info[:host],
:port => ssh_info[:port],
:username => ssh_info[:username],