Another point was that a Field ZimbraNetworkLicense with my old license was present on the LDAP. I logged with a GUI client to remove the field, but after this "fix" the problem was still present.
After a bit of additional digging I found that a limit for the number of accounts in the domain was set.
The solution was a :
zmprov md <DOMAIN> zimbraDomainMaxAccounts <NEW LIMIT>
Thanks all for your help