Well some more things I did (because I guess it's my fault):
I had XF 1.1.1 installed and a massive spam problem a while ago. So 1.1.1 had no comfortable way of batch processing that bunch of more than thousand spam users so I deleted them in the database directly.
For now I solved the issue by just setting the auto-increment value of the primary key to a higher one...