I tried running MS Outlook Repair Tool (SCANPST.EXE) on my Outlook.pst. It found errors, and corrected them, but no difference.

I just had some success with a couple of the contacts that didn't show up. I typed their email address into a "To" line. Outlook filled in their name. When I tried "look up contact" it denied having one. But, when I clicked "add contact", it did. One of them was added as a new contact, with none of my other contact info (e.g. address).
The other one, Outlook asked me if I wanted to merge with the existing contact. When I did, I ended up with the full contact, which was nice.
Both of these contacts now are findable in my contacts list. So, that seems like progress.