Ente is right - it's basically a handshake. When you want to send someone a message, your Bitmessage client requests their public keys from the network and then verifies that they are correct using the hash encoded in their Bitmessage address. The usual reason for getting the "waiting for encryption key" message is that the owner of the destination address is offline and their public keys are not available elsewhere on the network.

You can see a full description of the process on page 7 of the Bitmessage technical document, here:

https://bitmessage.org/Bitmessage%20Technical%20Paper.pdf

In the long term I'd like to see Bitmessage support non-hashed addresses (the address IS the public key), as was suggested by Greg Maxwell some time ago (see below). That would resolve this problem, although obviously the recipient of the message will still have to come online at some point to receive it.

http://www.reddit.com/r/bitmessage/comments/1kc03b/please_support_nonhashed_addresses
http://www.reddit.com/r/bitmessage/comments/1ay3kh/why_not_use_the_public_key_directly