What you seem to be asking for is some type of public-key convergent encryption, for which various schemes do exist.
However, all such schemes are unavoidably vulnerable to brute force guessing attacks if the number of plausible plaintexts is low — say, less than about a septillion ($10^{24} ≈ 2^{80}$).
Specifically, an attacker who has a convergent ciphertext (or just a cryptographic hash) of a message and the public key (if any) used to generate it can guess a plausible plaintext, encrypt it and compare it with the ciphertext / hash to verify whether or not their guess was correct.
A typical desktop CPU can do on the order of about a billion ($10^9 ≈ 2^{30}$) encryptions a second, so if there are fewer likely plaintexts than that, the scheme offers no real security at all. And if the attacker is willing to spend a bit more time and/or buy (or steal) a bit more computing power than that, they can probably brute force their way through a thousand or a million or a billion times that many plaintexts. Also, attacking multiple ciphertexts simultaneously in this manner is just as fast as attacking a single one.
A key stretching scheme may be used to slow down such attacks, but only at the cost of slowing down legitimate encryption (and decryption) operations by approximately the same factor. So for example, if you can live with a single encryption operation taking approximately one CPU-second, you can force the attacker to also take about one CPU-second (give or take a factor of 10 or 100 depending on implementation efficiency) to guess and test a single plausible plaintext. But that still means that an attacker with access to 100 CPUs (or possibly ~one fast GPU) can still test a million possible plaintexts in about three hours.
Typically, data such as mail addresses, usernames, phone numbers, etc. has rather low cardinality — and worse, even if there might be millions or billions of possible addresses, the likely address combinations in use are much fewer, and easily discoverable using public maps and address databases. So, in practice, using cryptographic hashing or convergent encryption to pseudonymize such data is doomed to fail.
What you can do, instead, is one of the following (in roughly descending order of preference):
Don't store or process such data if you can avoid it.
If you must store such data, store it encrypted (using a conventional chosen-plaintext attack resistant encryption scheme) and only decrypt it for processing on a secure system. Store the decryption key securely.
If you must pseudonymize such data, e.g. for processing by untrusted third parties, do it preferably by associating each datum (address, username, etc.) with a fully random identifier and storing the associations in an encrypted database. Make sure to keep this association database secure as described above.
Alternatively, you may generate the pseudonymous identifiers by applying a PRF (such as HMAC or some key-stretching KDF) to the sensitive data items with a secret key. If so, you must protect the PRF key from compromise, as it can be used to de-pseudonymize all data.
Either way, it is generally not feasible to do pseudonymization "at the source". Instead, you should encrypt any sensitive data using a secure public-key scheme at the collection point (which should only have access to the public half of the key pair), collect this encrypted data into a secure system and decrypt, process and (optionally) pseudonymize it there.
