Change node during saving it
After a long night of debugging I finally found the bug. I always thought that hook_node_presave is called twice when submitting a form. That is wrong. Took me a while to find out.

I then searched for node_save operations in my code through like 20 modules and found a module calling node_save in a custom node form submission handler. I removed it and it works now.

Thank you all for your help!