So the correct answer seems to be "we absolutely could link your searches to your identity, but we promise that we won't; however, you cannot verify that we are keeping that promise".
Which I'm afraid is not good enough. To be clear, I'm not saying that they are lying, and indeed I have no reason to suspect they are. But I'm looking for technological privacy, not contractual privacy.