Cannot connect to SSH server from Mac OSX
Problem was some weird DNS servers that have been configured. No new DNS names could be resolved. That's why it seemed that surfing the web does work - My usual web pages did work, but new ones did not.

I replaced the DNS servers with OpenDNS and everything works now as expected.

I don't know how the DNS servers were configured, but this resolved the issue.