Question regarding the assumptions of the No-Free-Lunch-Theorem for Search
I think that I was indeed misunderstanding something. Any search algorithm that wants to evaluate any point $x \in \mathcal{X}$ through $f$ would implicitly add $(x,f(x))$ to the histogram $d$. For example, one could design a hill-climbing algorithm in the following way:

for a solution $x'$, visit all neighbours $x_1,\dots,x_n$
afterwards, $(x',f(x')), (x_1,f(x_1)),\dots,(x_n,f(x_n))$ are all part of the histogram $d$
choose the best neighbour from $x_1,\dots,x_n$ by computing $a(d) = \arg\min_{x=x_1,\dots,x_n} f(x)$, which is independent of $f$ since $f(x_1),\dots,f(x_n)$ are already known
repeat