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.