Whose public key is used to encrypt email from email@example.com to firstname.lastname@example.org? My email client can't have the public key of every person in the world I could possibly write an email to at any moment, but then again if each email service had one public key for more than one account holder, there seems to be the possibility that one account holder could intercept emails intended for another account holder and decrypt them if they're encrypted with the same public key that both account holders use.
GPG, the only system I'm familiar with, makes you find a user's public key, import it, and mark it as trusted (by signing it). You don't have to share the signature if you don't want to.
Encryption with one of the keys public/private key pair is always decrypted with the OTHER key.
So in your example, if the mailserver has everyone's public keys, then anyone can send a message to anyone encrypted with my public key. Only I (the user with both the private key AND the password) can decrypt that message.
Now if I encrypt something with my private key and password, anyone can decrypt that message with my public key. The idea is that only I could encrypt a message with that key, so it's called a "signature." (Usually you send a copy of the message in plaintext but you don't have to.)
So if I want to send you a message that only you can read and want you to be fairly sure only I could have sent it, I would encrypt my message with my private key/password, and then encrypt it with your public key.
You would decrypt it with your private key & password, so that only you could read it, and then you would decrypt it with my public key, so that you were reasonably sure it came from me.
We would also have to arrange one last step - that you and I had talked before so that you were sure my key was mine and your key was yours. Usually a phone call works for that too, depending on your standards.
(I say "reasonably" sure because someone could steal my key and threaten me with jail/beat me with a rubber hose for not sharing my password, but that's another problem for another question.)
My public key is very easily located by my email address (and you will see "Benanov" in the comment field / username field, I forget which). Feel free to send me a message if you want to test this.
The easiest secure way is to send a signed email to the recipient you want to encrypt a message to asking them to reply with a signed email. Their reply will include their public-key which is what you need to encrypt email to them. You will want to verify that it was them who replied and not an intermediary either by having them verify their key or cert fingerprint through an alternative channel (say SMS, phone call, fax). At that point you are done.
Alternatively if your receipient's key is registered with a CA you could look them up by email in the CA's LDAP server (VeriSign allows customers to opt-in to publishing their VeriSign issued email certificats in their public LDAP server)