(I'm on the Diaspora* instance managed by the man who'd headed up Xanadu/Australia, which may have something to do with that.)
I suspect if I'd been paying closer attention to the Whole Earth / WELL crowd that might stretch back to the 1980s, and I believe Nelson's work featured there.
Google's Ngram Viewer seems to place peak Project Xanadu about 1990, so my own awarerness may not be the best guide:
<https://books.google.com/ngrams/graph?content=Ted+Nelson%2C%...> (Note that "Project Xanadu" is weighted 7x "Ted Nelson", so that both terms cover roughly the same vertical span
That said ... I think Nelson's vision is more concrete than, say, "Cluetrain", though as describing a technical project, realisation of that vision has been ... mixed. (Project Xanadu does actually exist, though it's little used.)
See also the works of Ted Nelson for a similar vibe.