I tried searching about two dozen of the new contacts and they all worked fine (though I could have just not spot checked the right ones). Most of the old ones are normally searchable as well, but just some random poking around I found at least 5 that aren’t functioning. It’s a small number, and seemingly random other than that were created by the inactive user.
The search functionality for the same contacts in standard Salesforce is normal.
I found this however in the developer console!