Your first option brings back horrible memories of servers locking solid blocking on downed NFS servers. Anything that blocks fs operations is dancing with the deadlock fairy. (I'd say that if someone modifies a directory on which a cookie is held, that cookie is invalidated. It's not like there are meaningful guarantees for readdir() on directories under modification even in the local case.)
I don't see why the client doesn't just remember 'the last filename we readdir()ed' and hand that back, probably in addition with a crude, random, non-stable cookie generated by the server in *its* last response in the same opendir() loop. I suppose it would make the readdir request a bit bigger... but in the common case of readdir()s following each other in quick succession it need be no slower: the server could keep a bit of extremely temporary local-only state (basically a readdir() handle and the random cookie we sent back with the last response) for recently received readdir() requests, compare the incoming request with the random cookie and filename, and now we know the next name to use, expiring the pair when we hit the end of the directory. If we expire the cookie/filename pair (which should be rare enough), we just need to opendir() the directory and readdir() through it until we find the filename again.
What am I missing? (Other than the fact that we can't change NFS because it's already there and doesn't work this way.)