I asked for two reasons. First, if it did hold, then your graphs would look somewhat similar to the binomially random graph $G_{n,1/2}$. This could be useful since pseudorandomness can be a very powerful property and there's probably a heuristic out there that exploits it. Secondly, it would suggest your graphs are likely to have clique number less than 20 or so (since $2^{-20}\cdot 5000 \ll 1$), so it would probably be worth running tests for $k=20$ before running them for $k=50$. But if it doesn't hold then never mind.

Silly question: is it true that if you have a set of $t$ vertices, their common neighbourhood has size roughly $2^{-t}\cdot 5000$? (For values of $t$ which are small enough that you can test this easily.)

I don't think that's a big problem, though? When I say that $G[N(v)]$ should have many vertices of low degree, I mean low degree in $N(v)$ rather than in $G$ itself. So the approach should only fail completely if every pair of vertices has a large common neighbourhood.