Some time ago I was interested in the same question, but for the strengthened, bi-Lipschitz case (mentioned above by Bill Johnson). For non-amenable groups it is true; Victor Guba told me how prove this, using Gromov's criteria of non-amenability. Also I was told that this result was obtained in a work of Benjamini and Shramm (I don't know the paper).

For amenable groups of exponential growth the answer is unknown to me, but I am very interested in it.

It is also interesting if the same hold for the following little more general case. Graph $\Gamma$ is non necessarily a Cayley graph, but a rooted graph $\Gamma$ that has exponential growth and such that the natural action of $Aut(\Gamma)$ on $\Gamma$ is vertex-transitive.