(similar to standard hashes, The only problem, IIRC is
that public key algorithms generally don't generate the
same results on the same piece of text 2 times in a row.)
That's deliberate - most PK algorithms add a salt value to
the plaintext to avoid any weaknesses due to repeat-encryption.
If you just do a plain PK encryption (RSA sounds like a good
idea given the patent expires in about a month) then it is
repeatable (for hash purposes) and decryptable given the
secret key.
If you would rather stick with something like PGP though,
you could always encrypt the password when it is changed,
but keep a hash of the password as well for verification.