open the Kaymera telephony/messages application, 

move to the contact tab (don't stay on the history calls tab), wait few seconds letting The contacts list load all the contacts, then perform the search. 

most of these issues are because user has a long list of contacts and it take time to load them to the application and differ between secure and not secure contact. 

During the time it takes to load the contacts, the search is not working well.