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...
at the moment new users can't register in my forum.
The error log says:
Mysqli statement execute error : Duplicate entry '1221' for key 'PRIMARY'1 minute ago - library/Zend/Db/Statement/Mysqli.php:214
Must be the user table I guess. Any ideas? THANKS!