a contact no longer shows up in imessage

This post talks about same but in Contacts, even if you don’t have Contacts being effected there idea of a Forced Restart may still help.

https://forums.imore.com/ask-question/376441-ios-10-contact-search-problem.html

This one also talks about it possibly being a Spotlight issue, again might be worth a read.

cannot search messages after upgrading to iOS8!!!

The only Messages I’ve had so far is to do with missing names on a few discussions, only there numbers show, this was sorted by going to Settings/Contacts and messing around with Sort/Display Order and Short Name settings, basically altering then changing back, it might have to be done a few times to catch though. Appears this altering things kicks something into action, but not sure if it will work for search issue, still might be worth a try.

Sort and Display Order don't have to be the same if it applies just to the Contacts App, but didn't think if it would influence things under Messages, you might be on to something. If it's sorted your issue you might want to post your finding on the other discussion so others could try, as I said, haven't had that issue yet so can't test.