I have a problem understanding the sence of a revocation certificate in gpg. If I create a revocation certificate of my key, if its stolen or lost, I can import it and my key is now revoked. If I upload my key now to a keyserver, my key should not be valid anymore, right? But anybody who has already my key, before I revoked it, can still encrypt messages to me, and the one who stole it can still decrypt the messages. Only new people, who download the key after the revocation from the keyserver see that the key is revoked and not valid anymore. Am I right with that?
Yes, you're right. The revocation certificate is a means to mark your key as invalid - in case you lost your secret key, or that your key has been compromised.
Of course, this information has to be passed on to all senders. Thus it is good practise to occasionally update all public keys from a key server - this adds all new signatures, new e-mail addresses, etc., and imports revocation information (if any).
In case that you are afraid that some adversary might intercept messages, it is a good idea to inform your common contacts (e.g. by mail) to refresh your key from a key server, or by sending them the revocation certificate directly.
A means to force your communication partners to update your key (at least from time to time) is by giving your key an expiration date. If the date approaches, you can modify your key and set a new expiration date. After that, upload the modified key to the key servers. Your communication partners will find out that your key has expired and will (hopefully) look for an updated key on the key server. This gives them your key with a new expiry date, or the revocation information.