I had this problem today (and have had it before) on a network share (not the ST3 folder) when importing a song into ST3 via Files. While it was done within ST3, it's still the Files app that is doing the searching. Could see my files and it worked to scroll through the long list of songs, but the list went emtpy when searching.
I just loaded up Files separately and tried a search within two directories. It worked for a file within my iCloud folder, but in another folder withing OneDrive, it wouldn't even find the one and only file it contained.
Files App has been problematic before. It also caches network connections and I usually have to disconnect and reconnect a connection to see updated root shares.
Tested now on iOS 15.3.1 on iPad Pro 2021, but it definitely gives me trouble on my other devices.