It only has to be unique. It's easy to find out who you gave it to by looking at the very first email.

ROT13 or the date in base36 (to keep it short) might help when you need to spell your email address over the phone. Today is oaf@example.com.