IPhone – Merge old exchange contacts to iCloud (with iPhone)

The data stores can get confused. It's usually a server issue but you seem to have narrowed that out by the details you posted.

Giving the iPhone a totally fresh database then re-establishing sync often helps when the databases are failing to sync correctly.

Since there is no way to just start over for contacts only, you have a short dance of steps.

1. Disable all contact syncing over the air.
2. Power cycle the phone
3. Use a test account (i make a new user account on my mac with an empty address book) - syncing from iTunes to overwrite all contacts stored on the phone clears the data store well. You can have iTunes only overwrite the contacts and not affect any other data on the iPhone.
4. Sync back to your main iTunes if desired, then finally re-enable contact sync over the air.

Since the contact database gets restored from a backup, restoring the phone won't cure contact database errors. If you can re-set up the phone, you could restore and set it up as a new device also.

From http://support.apple.com/kb/HT5058 :

Data stored with iCloud will not interact with your Microsoft Exchange data, while likewise your Exchange data will not interact with iCloud data.