Sounds like a bug.
Unless you have had another instance of marketo at your company. That has happened to our team, we've had multiple marketo instances due to mergers and acquisitions, and have had to use different versions of our email address.
Have them try logging in with that user and resetting their password if needed, and then see whose instance of Marketo they are in
Also, if you have a sandbox make sure it's not already in use there.
I'm getting the same error even though deleted the user from sandbox environment.
This userid is in use. Choose another email
But same user can have account in multiple instances.
Like I can have my account in both sandbox and prod instance. Is Universal ID used for such needs ?