Here's what I do since I live in the same environment.

Do just like what you described above, then:

Get putty tray after install:
http://www.xs4all.nl/~whaa/putty/
You can read the improvements on the site.

Also, install launchy:
http://www.launchy.net/

Then the putty plugin for launchy:
http://sourceforge.net/forum/forum.php?thread_id=1840503&forum_id=677087

Now I just hit the "alt-space" type in "ssh " and viola connected.

I also use xming for a X-Server:
http://sourceforge.net/projects/xming.

Cheers,
eric