|Do you know where your variables are?|
The best solution should of course be to encrypt on the serverside and use SSL - but that has the drawbacks you mention above.
When retreiving lost passwords: Depending on what kind of users you have, you could possibly have the user that lost the password enter his/her email address instead, which will then be matched to a user and emailed just like above. Reason for this is, that on many sites, the usernames might be known, but not the email addresses. So the black hat dude would have to figure out a valid email first, and then succeed in sniffing it (unless PGP is also on, in which case it hardly matters). Drawback is that some users tend to forget what email they signed up with...
Some good thoughts there, but it would seem that for tight security, there is no good replacement for encrypting all the traffic, which has lots of penalties in performance, price etc.
One also always must ask oneself what is a reasonable security level for the particular site, and weigh risk/gain against each other.
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.