@JP-d, I made a test route online (on PC), then on my phone entered the search (without even syncing routes!) and got this:

The newly made route was found by keyword. This proves that the search tool actually does look into your database ;-). Now the question: why did it not do that in your case? My guess is that the search tool looks into the online library and you probably did not have an internet connection at the time. Correct?
If I repeat my search in flightmode, I indeed get no results from the online library.
If I repeat my search after a succesful sync, in flightmode I still get no result.
This proves that routes are searched for only ion the online library, and not in the locally synced library.
If I repeat the test after having started the route once, return to flightmode and search, I see that the route actually gets found. So the search also searches in local recents.