I found a small workaround for the bad search (which may be obvious for some, and it won’t work for all apps).
Lately I also got the update to Aurora Store 4 and had to install an app that’s solely available via Google Play. I just couldn’t find it in the Aurora Store. There are different variants of this app which were shown in the results, but the one I wanted wasn’t showing (it’s a money transfer app and every bank has an own variant). I even checked the ID of the app on my other phone and typed this into the search, but no dice. A lot of variants where shown, just not the one I was looking for. And mind you, I tiped the full name of the variant.
So I went to the website of the developer, searched for the store link (The *Get it now on Google Play" style button) which brought me to the Google Play page of the app.
I then opened it in the system app via the browser menu (using Firefox). I selected Aurora Store as app and found myself on the page for the desired app in the Aurora Store and was able to install.
A second App I needed was found directly and installed just fine, so sometimes it’s just working as desired.