You are correct that the User API requires unique email addresses. The site also requires unique email addresses when joining via the user interface. This is a requirement of the underlying ASP.NET membership provider.
Aside from directly ensuring each user has a separate address, you could also try adding a + to mailbox names to make them distinct. i.e. firstname.lastname@example.org, email@example.com, as these should technically resolve to the same mailbox. Additionally, Gmail allows adding periods anywhere within the username portion of email addresses.