A few users have mentioned contact searches taking longer that usual or new contacts missing from their mobile. This seems to have started after a resent update. I have 2 solutions.
1) Use spotlight search. This is a separate index and does not have the same slowness as contacts. Access spotlight search from the app screen on your device; place your finger in the center of the screen and swipe down to search.
2) Go to Settings > Mail > Accounts > Choose the exchange account > Turn off contacts > Choose “Delete from iPhone” when prompted
Wait until they are deleted and turn contacts back on. The rebuild will take about 20 minutes.