Is it possible to associate a secondary email address with an existing *public* key?

You can add aliases to ~/.gnupg/gpg.conf by abusing "groups":

group [email protected] = [email protected]

In new versions of Evolution (tested with 3.22.6) the recipient is passed to gpg including angle brackets. Those must be added when defining the group:

group <[email protected]> = [email protected]

Docs here: GPG Key related Options

Actually, Simon is wrong. You can add new user IDs and revoke old ones on an existing key. Attempting to masquerade as others aside, it would achieve very little to prevent this type of modification since the worst that can happen is that someone receives an encrypted message that they cannot decrypt. At which point they would discover that someone is playing games.

However, if a key has been signed by a third party and then a second UID is added to the key, the previous signatures are not applied to the new UID. You can actually see evidence of this on my key (0x321E4E2373590E5D) because I added two UIDs to my current key earlier this year.

Grawity's recommendation of using group lines is the quick and easy way around the UID disparity issue, especially when the other party either doesn't know how to update their key or doesn't care.