In outlook Make a new folder for contacts called backup
move all contacts to the 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.