This is possible with scripting. A variation is also possible with a secondary table.
Given all of the requirements, it is not possible with only a formula field.
A script can search records to see if the email address is a repeat. If the email address is a repeat, get the corresponding unique id and put it in this record. If it isn’t a repeat, the script can generate a random unique id.
On the other hand, some people are not comfortable with scripts.
A non-scripting possibility is to use a second linked table for storing email addresses and unique ids. In this second table, have the primary field be the email address as a single line text field. When a new email comes in, copy the email address to the linked record field. If the email already exists, the link will be made. If the email does not yet exist, a new record in the email addresses table will be created. Each email address will only appear once in the table. (You may need some tweaks to make email addresses lower case to ensure uniqueness regardless of case.)
To generate the unique id for the email address, use the Airtable record id, an autonumber, or the creation time (if emails are created infrequently enough). These unique ids will not be random, although a formula field can make them appear more random than they are.
Finally, bring the unique id to your original table with a rollup or lookup field.
