I can reproduce this behaviour every time by just clicking Quick Edit and then Update without any modifications in quick edit form. Bulk edit also breaks linking.
All other plugins are disabled, but even if they were not, none of them could interfere with saving of pages. I know because I wrote them.
The only point in which I’m hooking on save_post action is in my theme but there I check if post type is my CPT and if it’s not return immediately.
To prove this I just switched to twentyeleven theme and result is same.
I did direct SQL queries on wp_postmeta table that revealed missing or incomplete _translations values.
For instance – there are two pages linked as translations:
id: 67, language: lv;
id: 82, language: en;
(no tags, no other meta or anything)
before quick editing, query SELECT * FROM wp_postmeta WHERE meta_key='_translations' AND post_id IN(67,82)
gives:
271, 67, _translations, s:34:"a:2:{s:2:"en";i:82;s:2:"lv";i:67;}";
273, 82, _translations, s:34:"a:2:{s:2:"en";i:82;s:2:"lv";i:67;}";
now they are linked and all is right, but after quick editing page with post_id 67:
273, 82, _translations, s:20:"a:1:{s:2:"en";i:82;}";
It seems that Polylang_Base::delete_translation() is the only method where delete_metadata is called for _translations meta key.
Regarding quick edit support – it’s easy, but involves some JavaScript trickery which is exactly the way it’s done in original quick edit.
It is well explained on codex action reference page quick_edit_custom_box.
You could put your language codes as hidden elements in custom columns and then set up form elements in quick edit accordingly.
From PHP coders standpoint it may seem rather awkward to populate form fields from table cell text, but it works and reduces data amount from server.