This works most of the time with corrupt contacts:
In outlook Make a new folder for contacts called backup
move all contacts to the backup folder and wait for all to be removed from device
then pull battery on device and put back in
After device boots move contacts from backup to the contacts folder and wait for them all to appear
Make a new contact in outlook and see if it gets to the device and check with an edit too.