This initial message is what Monkeysphere is designed to fix.

Monkeysphere distributes GPG-signed SSH host keys. If you have the admin's trusted public key, and they sign their hosts' keys, you can trust the host key even if you haven't connected to it before.

http://web.monkeysphere.info/

Fortunately, for those of us who are a few years younger, there's Oolite.

I have similar platform requirements (less the Blackberry), so a combination of PasswordSafe and pwsafe (which is a compatible command-line version) meets my needs.

The two "hoped for" features that you listed, command-line client and synchronization, are hard requirements for me, which pwsafe meets.

Speaking as an admin, I've seen way too many end users click through certificate warnings for self-signed certs without understanding what they are doing. Firefox is doing the right thing (and now that IE 8 is doing something similar, I'd say they aren't the only ones who think so.)

...to rhyme with 'atrocities' ?