This is the exact same problem I have with DuckDuckGo.

I still use them, but they could be logging everything, for all I know.

It would be great if they were regularly and frequently audited by a third-party who has earned widespread trust and respect, like the EFF. Not that the EFF is in the audit business. But serious auditing of sites that claim to respect privacy is sorely needed.