This is why I have resorted to 3rd party solutions such as copytrans contacts. Used it to place my contacts from my two email accounts and combine them with the ones on my iPhone - this essentially avoided the need for using Exchange sync.
Originally Posted by Matlock
Once you have all your contacts on your iPhone, you can then turn on iCloud which will bring all the contacts into your Apple account from where you can achieve ongoing sync.
I am referring to copytrans contacts because in addition to bringing all my contacts to my iPhone, it has also allowed me to place my contacts into groups (i.e. Work, Family, etc) on the iPhone itself and to keep a safe offline backup of my iPhone contact list on my PC (in case something happens to the iCloud).