Using New Outlook on Windows for professional communication and productivity
Although this is not a fix, it's a way to at least not lose your contacts completely. This would work to backup your contacts IF you can search for a contact and it appears (only to disappear later.)
In the "People"page and "All contacts" is selected, click "Manage contacts" at the top right of the window. Click the "Export contacts" drop-down. Then click the Export button. That will create a CSV file, and in that file you'll see all your contacts! They're probably not usable in that form, but at least it preserves the data.
Good luck,
Jerry Abrams