Great feedback from everyone. I guess it's a small consolation to know that I'm not being overly-paranoid. I am really going to have to re-think my usage while on untrusted computers.

Internaut, carrying a Pocket PC is definitely a good, albeit expensive, solution. Do you ever have difficulty finding WiFi signals to use? It seems like there are still an unfortunately large number of airports and hotels that lack WiFi, and those that have it are rarely free.

Scandalous, I like your scheme to interlace the characters of your username and password while typing them in. Brilliant! I'll definitely keep that one in mind.

JadedTraveler and ScottC, the idea of using the WinXP onscreen keyboard is also an excellent one that I had not thought of.

I think the thing that is most frightening is the idea that if someone were to intercept one of my passwords (either through keylogging or other means) they could potentially take control of that account without me ever knowing.

It seems like a simple way to address this would be for sites to send an alert to the (original) email when anything changes in an account. That way if someone were to maliciously gain access to an account and change the password and/or email address associated with that account, the site would send an email notification that would make you immediately aware of the problem so you could take action before any substantial damage is done. It appears that Paypal does this, but surprisingly, none of my credit card sites nor my online banking site did so.