A PDA is definitely a safer way to go. If it ever gets "hijacked" in any way, you're probably not going to ever see it again, so snooping software is not a big concern. On the other hand, simply using the Password Safe program at all renders you vulnerable to a known ciphertext attack. I don't know anything about the particulars of the algorithms it employs, so I can't comment in any greater detail. Even your setup would still make me a little worried, but I'm way more paranoid than most people, though not for any particularly good reason.

I actually like to use my PDA to carry around a list of SSH key finger prints, so I can verify that when SSHing into a machine for the first time that I'm not having the connection hijacked via a packet rewriting attack. Of course, I'm hardly ever on a computer where a key isn't already cached, as I refuse to type in passwords at other people's computers. Typically the need only arises when I build a new machine, or rebuild a machine from scratch, wiping out the list of cached host keys.

The only effective attack against my fingerprint storage and verification mechanism would be to generate "fuzzy" fingerprinted keys, i.e. ones that had fingerprints very close to mine, put those on a machine, and not only hijack my connection with packet rewriting on some router, but also to momentarily steal my PDA from my pocket and rewrite the file that holds the fingerprints. This seems ridiculously implausible, even by my standards. :-p