It's much more fundamental than that. To implement the READDIR request, or anything like it in a stateless protocol (ignoring here hypothetical protocols which can only return the whole directory in one go, since they would have obviously terrible performance), you must be able to ask for 'the next bit of the directory from where I was readdir()ing last' even though the server has no idea where you might be in the directory because the protocol is stateless. NFS does this by handing you a cookie with each READDIR response which corresponds in some way the spec does not specify to the location of that file in a readdir() response, so you can pass it back in the next request and get the next filename.
And that cookie is, of course, an (encoded) return value of telldir().
Worse yet, because NFS is stateless, *any* nonpersistent telldir() cookies are going to fail with NFS: the pathological case of someone who does a telldir() and then a seekdir() much much later in a different call to opendir() is downright *common* if you've got an NFS server looking at that filesystem.
Which means that every NFS-exportable fs (any serious FS, period) needs a way to encode positions in all directories, stably, into a 32-bit number, with vaguely reasonable things happening to those positions even when the directories change. It's a complete pig on a lot of filesystems: they sometimes need whole extra data structures just to make this one system call work. But, as Neil says, something like it does indeed seem to be essential if you want stateless network filesystems of any sort to work. I wish there was a better way, but I wish for a lot of impossible things.