Newly-created contacts in Outlook don't sync to iPhone
In the case where you don't have a specific failure message or error, it's often best to isolate where the problem lies.

If you were using iCloud, I would recommend you add a contact from your computer then log into the web interface of iCloud to see that the change propagates to the cloud.

If it does, then you will know to focus on the cloud to iPhone part of the sync. If it does not, you can know that Outlook (or the PC end of things is failing.)

You can try these two things:


Set up syncing again on the guess that iOS isn't set up properly
Get access to the servers that are syncing the information and dig into the troubleshooting or logs that are available there to determine where the break down is happening.