Selection are lost during edit

When we edit a list with selected key|value pairs we can select values correctly.
And they appear on the saved node.

However - If we edit the page again, the values that were selected are back in the "available list"... but added to the bottom of the list.

I moved the site to a different server and everything works as designed.

Both are Drupal 7.43
All Modules are up to date

MySQL ver 5.5.43-log vs MySQL ver 5.5.49-0ubuntu0.14.04.1
PHP Version 5.3.17 vs PHP Version 5.5.9-1ubuntu4.16
Apache/2.2.12 (Linux/SUSE) vs Apache/2.4.7 (Ubuntu)