That problem seems very solvable if they don't need to monetize your data. You might, for example, turn off search history and the use of search history to guess what you might mean with new searches.

Turning search history off doesn't mean that they stop recording in in their database.

I have no way to verify that.

Kagi keeps track of all queries because they are charging you for each one or removing from daily quota

Kagi keeps track of query count, not the actual queries.

I really doubt that using Google while not logged in is more 'privacy friendly' than anything else, given their ability to track with pixels and shadow profiles. In any case I don't particularly care about that issue, I'm not searching for bomb-making guides or anything.

What I care about is a search engine that's trying its hardest to serve me answers to my searches, rather than feeding me ads.