Mullvad has built trust over many years. There is always someone who knows what you are searching for. The search engine will not accept an opaque blob of encrypted data as a search term, after all.
The trust comes from them being a small player. The moment they get big, govt will come knocking, and they'll be just like anyone else.