Duplicate contact storages
The weird problem had a weird solution. I turned the phone off and turned it on again, and the problem was gone.

I can't give any reason as to why the problem occurred and why it got solved. Might be a bug.