I recently removed some code that stat'd 4000 files over NFS. It took ~5 seconds, so it wasn't as bad as you say. Also, I'm pretty sure NFS can do better if you tune it.
Found this [1], which might be helpful. The linked python program shows really high numbers for me though. Hopefully it's incorrect or I just misunderstand what the numbers mean.
What you are saying is 1.25ms on your network (5000/4000). That's twice as fast but still significant.