"All services have to keep some track of who made which query in order to get them the right results back (we don't want people asking for cat pictures to get non-cat pictures back). "
Why should this be the case?It's perfectly possible to perform a search for some user and delete all data about the process afterwards.