> you could of course just use <random string>@yourdomain for every login

You could also use the hash of the domain name with a secret salt value. Then if you somehow lost your login info, you could still figure out what your recovery address was if you still knew the salt.