Agreed: Teams search is not the best one currently. However, there has been some improvements that will help to find information and messages better.
Searching with partial words
While this was a pain earlier, this has gotten better. Originally I thought Team’s search would work in 5 character blocks, but it seems to be more about matching a word (or a partial word) to a some kind of dictionary list and then looking for content via that. Effectively: you can get lucky when searching with incomplete words. Like you can search using word share to find SharePoint. But if you search with shar, sharep or something like that: you don’t get any results. Remember: wildcards don’t work so you can’t search for share* and you can’t search with point to find SharePoint.
You can try your luck with Microsoft Search for Bing
Bing can also find some results. The rules seem to be slightly different. I expect this to improve over time. However, there are cases when you can find some content using Microsoft Search. And remember: this is the only search, at this point, that can find the messages from both Teams and Yammer.
The best: Use the mobile Teams to find the messages you are looking for
The best way to search and discover Teams messages is the mobile app. Unlike desktop/web/Microsoft Search this one looks for combinations of characters even inside the word. As it should be. While this is still a plain text search, it is fast and it works.
Looking for files?
Searching for files seems to use shared Office 365 (was SharePoint) search. Yes, you can use wildcards if you search for files. In Teams the search focuses only on files in your teams, so you might want to hop onto Office 365 using a web browser and start looking for files. It’s filters are also really useful.