Here is an issue I see on my Debian NFS server running the current XFS
devel tree and the userspace NFS server. The server is running
linux-2.4.0-test11-XFS and the client is running linux-2.4.0-test10.

server# cd /archive
client$ cd /archive
server# ls
backup  doc  media  nfs
client$ ls
backup  doc  media  nfs
server# mkdir test
client$ ls
backup  doc  media  nfs
client$ cd test
client$ cd ..
client$ ls
backup  doc  media  nfs
server# mkdir test2
client$ ls
backup  doc  media  nfs  test  test2
server# rm -rf test*
client$ ls
backup  doc  media  nfs  test  test2
client$ cd test
bash: cd: test: No such file or directory

The problem, of course, is that directory creations and deletions
don't immediately take effect on NFS clients that the filesystem has
been exported to.