Scalable mechanisms to support efficient key-based search in distributed systems are an important part of the infrastructure of peer-to-peer systems and global information systems. They received substantial attention both in information and communication systems research. A particularly important class of approaches is based on a principle of scalable distribution of binary search trees that has been introduced by Plaxton \cite{PLAXTON}. When adapting the shape of such a tree search structure to the data distribution in order to obtain load balancing, the search trees may become highly unbalanced. We show that for P-Grid, a Plaxton-like distributed search structure that we first introduced in \cite{PGRID1}, the expected communication cost for searches is strictly limited by $\log(n)$ where $n$ is the number of peers. This result is completely independent of the shape of the underlying tree. The approach exploits the randomization principle of the P-Grid structure by virtue of its decentralized and randomized construction process.