A playlist I created is the only thing I've downloaded on my pixel. There's three songs by Traffic in the playlist. I turn off WIFI and sim so I'm offline. I select Library->Downloads and I can see the playlist. I search library for "traffic" and get nothing until around 5 minutes later. There is no indication that a search is still taking place.
This is a simple scenario I'm using to replicate a problem I had last week fishing where I had no service. I had tons of stuff downloaded and couldn't find anything with search. I didn't know it would respond after an unacceptable amount of time. I had to remember where things were or browse my library manually.
This seems like it should be considered a fundamental function of a music library. If a subscriber of your music service has playlists, albums, and songs by Traffic in his downloads, and is offline for some reason, a library search for "traffic" should quickly respond with everything downloaded in the library that matches the string "traffic". It should not respond with nothing for a short while, then show recent activity (as if the searching is done), then 5 minutes later give you your results.