I seem to have fixed the problem of losing all Contact entries (from Exchange ActiveSync and Voip/IM accounts) after reboots that I described in this post.

The fix was simply to backup my device, reflash it, including the eMMC via these instructions.

Upon re-starting the device, I then used the built-in Restore feature to restore Bookmakrs, Settings, and Application List. I made sure NOT to backup or restore Communications and Calendar, since that was the data store that seemed buggy.

All my Contact entries re-appeared after the first sync with Exchange ActiveSync (to Hotmail). I've rebooted several times, and all Contact entries are preserved.

Hope this helps someone.