Yes, search and autocomplete are being continually improved.
100% understand the concern when you see new PDS hosts being added, especially if you've been burned before.
But one of the key design goals of Bluesky is marrying usability and decentralization (which brings many exciting new features!)
We devs will jump through hoops so that the app Just Works™️