There is a "secret" keyboard shortcut to force an exit :~) From the frozen session, hit these keys in order: Enter~. The tilde (only after a newline) is recognized as an escape sequence by the ssh client, and the period tells the client to terminate it's business without further ado.
The long-hang behavior on communication issues is not a bug, the SSH session is hanging out hoping the other side will come back. If the network breaks, sometimes even days later you can get an SSH session back. Of course you can specifically tell it to give up and die with the sequence above. There are also various things you can do such as setting keep-alive timeouts in your client so that if it doesn't have an active link for a certain amount of time it shuts off on it's own, but the default behavior is to stay as connected as possible!
Edit: Another useful application of this interrupt key is to get the attention of the local ssh client and background it to get back to your local shell for a minute —say to get something from your history— then forground it to keep working remotely. Enter~ Ctrl+Z to send the ssh client to the background job queue of your local shell, then fg as normal to get it back.
Edit: When dealing with nested SSH sessions, you can add multiple tilde characters to only break out of one of the SSH sessions in the chain, but retain the others. For example, if you're nested in 3 levels, (i.e. you ssh from local->Machine1->Machine2->Machine3), Enter~. will get you back to your local session, Enter~~. will leave you in Machine1, and Enter~~~. will leave you in Machine2. This works for other escape sequences as well, such as moving the ssh session to background temporarily. The above works for any level of nesting, by just adding more tilde's.
Finally, you can use Enter~? to print a help menu of available escape commands.
TL;DR - the supported escape commands are
Supported escape sequences:
~. - terminate connection (and any multiplexed sessions)
~B - send a BREAK to the remote system
~C - open a command line
~R - request rekey
~V/v - decrease/increase verbosity (LogLevel)
~^Z - suspend ssh
~# - list forwarded connections
~& - background ssh (when waiting for connections to terminate)
~? - this message
~~ - send the escape character by typing it twice
(Note that escapes are only recognized immediately after newline.)
Best Answer
From the comment discussion this sounds like the behavior you see when you are experiencing packet loss due to MTU/fragmentation issues:
http://www.snailbook.com/faq/mtu-mismatch.auto.html
This usually shows up as being able to login to the machine but some commands fail (usually a significant percentage of the time). You can verify that this isn't the issue by getting the same behavior on a machine connected to the same LAN as the box having the problems. If that session works fine, then you probably need to start looking at the network layer between you and the machine in question.