After speaking with the support it is a multi server issue,
Enable the Webfarm as it enable a process of update the cache across servers.
All Kentico providers implement AbstractInfoProvider, which ultimately implement IInfoCacheProvider.
This cache provider put the object in a Kentico cache named HashTable (I don't think it is the same cache you can use with CacheHelper).
This cache is a dictionary style cache (key/value), it cache the user when there is a new one, or when someone login, but more importantly it caches the user when it is not there. (e.g. dictionary[key] = null).
So one of the scenario of what happened is:
1. A user try to login on his computer on server A, but he does not have any account, the custom authentication don't find him, set the user to null (the key is added to the HashTable cache with null)
He then register with his phone on server B, which add the user to the CMS User table and add to the HashTable for server B only.
He then try to login on his computer again on server A, the custom authentication find the user account, set the user (as per documentation).
Finally the UserInfoProvider search for the user in its HashTable, find it with the value null, therefore it tries to add the user in the CMS User table like it is a new one. And crash due to the duplicate.
So there must be a process in the WebFarm module that probably notice the other servers to update their cache when the current server do.