Hi Tobias,
I have talked to my host and they managed to figure it out.
This is exceprt from the error log:
[01-Sep-2012 11:51:56 UTC] WordPress database error Duplicate entry ‘16983-160’ for key ‘PRIMARY’ for query INSERT INTO es_term_relationships
(object_id
,term_taxonomy_id
) VALUES (16983,160) made by do_action(‘wp_ajax_autosave’), call_user_func_array, wp_ajax_autosave, edit_post, wp_update_post, wp_insert_post, wp_set_post_categories, wp_set_object_terms
[04-Sep-2012 22:18:13 UTC] PHP Warning: Unknown: Input variables exceeded 1000. To increase the limit change max_input_vars in php.ini. in Unknown on line 0
[11-Sep-2012 21:24:31 UTC] PHP Warning: Unknown: Input variables exceeded 1000. To increase the limit change max_input_vars in php.ini. in Unknown on line 0
[15-Sep-2012 08:33:07 UTC] PHP Warning: Unknown: Input variables exceeded 1000. To increase the limit change max_input_vars in php.ini. in Unknown on line 0
[15-Sep-2012 08:34:13 UTC] PHP Warning: Unknown: Input variables exceeded 1000. To increase the limit change max_input_vars in php.ini. in Unknown on line 0
So we set the max_input_vars to 3000 and everything works fine now.