After some setup problems -- indeed related to SSH keys -- I've successfully developed Rails/Sinatra applications on Windows and deployed those to Heroku. It works fine.
Generating the keys was a challenge -- I didn't keep notes, but I think I generated the keys with the Git GUI in which you can create a OpenSSH key. That key file is stored in ~/.ssh (so within C:\Documents and Settings\<account>\.ssh) as id_rsa with an accompanying id_rsa.pub. Since I wanted a seperate key for use in Heroku, I've renamed both files of the key pair to id_heroku / id_heroku.pub.
Finally, in the same folder, I've created a file config. That file contains
Host heroku.com
Hostname heroku.com
Port 22
IdentitiesOnly yes
IdentityFile ~/.ssh/id_heroku
TCPKeepAlive yes
User [email protected]