I think the crucial layer that we need to implement... a lot of things... is a global immutable (aka referentially transparent) namespace. Urbit is one project building such a thing; another one is IPFS. (Urbit names are addressed by identity; IPFS names are content-addressed; so they're complementary and not competitive.)
One of the reasons the Web seems like such a poor imitation of Xanadu is that it rests on this rickety foundation of a mutable binding from name to resource. Once global immutable namespaces -- Urbit, IPFS, anything -- are more widely deployed, I think Xanadu would be wise to use such a thing as a layer.
But to paraphrase a famous saying: grant me the serenity to accept the code I cannot rewrite, the courage to rewrite the code I can, and the wisdom to know the difference :-)
Theodore Nelson has said this himself, I can't remember the exact source but I think it was in his google talk he said that you need permanent addressing for Xanadu to work. He at least reiterates the concept (though with less principal importance) here:
http://xanadu.com/XanaduSpace/btf.htm
"STABILIZED ADDRESSES
Imagine that everything you type is given a permanent, immutable address. Then to refer to a given sentence, or paragraph, you would refer to its permanent address span (start, length). This would have many benefits.
This is not the way things are ordinarily done, but in this system we simulate such permanent addresses in order to get these benefits."
Computer Science is not renowned for it's diligent study of history. And that's just for those that actually study it in some form of institution, not all the people who "practice" it without any formal training.
That said, the fact that Ted Nelson/the publisher have stubbornly refused to just publish for example "Computer Lib/Dream Machines" free on the (inferior) web, or at least as a DRMed ebook or merely a dead-tree re-print -- makes it unnecessarily hard for people to read up on the concept(s).
You can still find copies on Abe Books but they're not cheap.
http://www.abebooks.com/servlet/SearchResults?isbn=091484549...
Glad I held on to this little bit of dead tree history even if it is the revised version.
Another lesson is to avoid too long a stealth period.
Urbit is 100% open source, and (as you mention in your other post) probably a good fit for implementing Xanadu on top. Our filesystem satisfies a lot of the requirements.
Want to build it? Great. We'll happily help.