Apple iOS – Move contacts from “On my iPhone” to Exchange
Apple iPhone syncing contacts with Microsoft Exchange server
New contacts default to the “On my iPhone” contact group, which aren’t synced with the Exchange account. This could cause contact loss when upgrading or switching iPhones, or will cause missing contacts on multiple devices e.g. iPads. I came across this earlier when someone mentioned their upgrade had missing contacts (turned out to be over 40). iOS version 5 seems to set Exchange as the default contact group, I believe this effects iOS 4 and below. You can change it in this location:
Settings -> Mail, Contacts and Calendars -> Contacts – Default Account
There are a few paid apps that can move contacts across the groups, or another popular solution is to “share” the iPhone contact and email it to yourself, from there you can save it as a contact in the right group. After a bit more digging I stumbled across Orbicontact which was free and has the functionality needed.
The contacts should now appear in Outlook and/or the new iPhone.