I'm sure there is a way to search, but I think Foobar is maybe built for a different kind of user than Spotify, etc.
https://www.foobar2000.org/images/img/main-black.png (ignore the white-on-black, that's orthogonal style change).
See that Filter box? That's a search that, within the scope of your music library, works better than Google's or Spotify's. It's an incremental search box (I believe web kids call that "Instant" nowadays?), that filters the album list by your search about as fast as you type.
I don't think it's built for "a different kind of user" - Spotify UI is pretty complex, because everything from search to managing playlists presents you with a pretty noisy UI that makes you click around a lot to find what you want and not click on what you don't want (Foobar never "suggests" you music it fully knows is not what you're searching for). Being a user of both - having switched to Spotify when it became easier than bringing an external drive full of MP3s to work - I can tell the basic UI interactions are of similar complexity, except Spotify is a bit more confusing at times.
Foobar's incremental search is such a useful feature I ditched Winamp for it back in the old days, and I still use it as a go-to example in product/UI development sessions.
Maybe in terms of the things you can click and knobs you can twiddle, but moving my music into Google Play and off (e.g.) iTunes means that I can very trivially put music on my mobile device (using either that device, or the computer) that is almost instantly accessible offline, and easy to listen to.
That twin gain - ease of sync and offline availability - completely blew Winamp and iTunes so far out of the water that they're in orbit, as far as I'm concerned.
(There are things I miss; multiple genres for a given song/album. Organizing by folder and playlist. Visualizations. Sometimes Google Play will forcibly replace my uploaded files with the wrong version - I still have a few songs that are "censored", and it grates me whenever I hear them.)
I've asked for open-source/self-hosted solutions before, and a few people here responded. One of the solutions looks like it promises to do what I want, though I haven't had a solid chance to look at it: https://news.ycombinator.com/item?id=19555899
That's devolution in multiple ways. Your app is now tied to your subscription so there's no competition for best music app. The apps are now high latency bandwidth hogs that require a network connection. Your now held to ransom, stop paying us and you lose your entire music collection.
Do they? Once something is a tool that meets a need, should the default assumption be that any change can be justified by vague appeals to "evolving", or should there be some specific and defensible justification required beforehand?
So... why hasn't the fundamental UX of the automobile evolved in the past half-century?
In the early 2000, my music library was a few dozens GBs played back using mpeg123 or something. Nowadays it’s a Google Play Music subscription. Things have moved to the cloud, a lot. That’s a huge change in how computers work, requiring some serious UX changes. I too hate gratuitous UI changes, but things need to keep evolving.