The search box only searches for chat history that has loaded. Due to pagination, the entire history is not fetched on first load causing the search box to scan only the most recent chats. This means that I have to scroll a bunch of times for the chats to be fetched and then I can use search. However, if I'm already there I just click on the chat I want. This has rendered the search box less useful at the moment.
The answer might be that searches need to happen server-side, which is bigger technical hurdle than it seems on the surface.