Ah, yes, of course, for the CAMs (or any other relevant longest-match index) you need to only store 64 bits at worst. Still, it's not the 5 fold saving.
The Cowen algorithm: Her original paper encodes landmark output ports in the label. That's not practical because of updating. However, with some added restrictions and at the cost of a slight amount of generality (e.g. not being able to work for every posssible graph, like pure star/hub-spoke graphs), you can eliminate that and have the addresses just be (landmark,node). You can do this by having nodes not build local clusters that are overly large, and so you can allow landmarks to also maintain local cluster routing tables - eliminating the output-port hack.
The (landmark,node) association need not change too often. Outages of links in the region between landmark and destination can be dealt with as they are today with routing - the scheme has full shortest-path routing in a region around each node. No need for the label to change. Outages that affect the path between the source and the landmark also similarly are dealt with like normal routing today. The one issue would be if there is a complete loss of a local cluster shortest-path route from the landmark to the destination. Then packets would disappear.
The end-node can at least be informed of this quite quickly, through the local cluster routing protocol (which can be a slightly modified BGP). Which is better than BGP today. Dealing with such issues of landmark redundancy, i.e., having associations with multiple landmarks, are perhaps better solved at a layer above the network layer. The theory shows that it is impossible to have both sub-linear routing tables AND full, global, shortest-path routing for /everyone/. If super-linear routing state is a problem you want to have solved, you have to give up something else.
Practice suggests that those who require redundancy at scale already seek to do so above the network layer. I.e. it is already good practice to locate redundant services on different prefixes precisely to guard against routing fsck-ups and failures. That suggests multi-homing in the "global prefix for one prefix" sense is not something that you should make too many other compromises for in any new routing architecture. Even with IPv4 which does do multi-homing for all to all, BGP multi-homing is not reliable enough to rely on. So it's probably better solved at the transport layer or higher, mediated at end nodes, and not complicate or compromise routing for it, as networks will still go and implement higher-layer redundancy anyway.
Indeed, by providing 2-way signalling in the routing layer, we can make the higher-layer redundancy solutions much better. Today if you advertise a prefix, you have no idea who has and has not received it, beyond your immediate neighbours. Even for your immediate neighbours, you still don't know if they have accepted the route. You can't really improve this in a routing system where all prefixes have global visibility, the communication and state costs would likely be unacceptable. However, in a Cowen Landmark routing scheme, we could at least provide an advertising node knowledge of which landmark nodes have working local cluster connectivity back to it. That's made possible because the scope is restricted, no longer global.
Note that the routing isn't source routing. Just because the address contains (landmark,node) doesn't mean the packet goes via the landmark. As a packet gets near to a landmark it may hit a node that already has the destination in its local cluster routing region, and so the packet goes shortest-path from there to the destination - potentially skipping the landmark. It's more two-stage routing, but each stage is shortest-path, per-hop routing. The 1st stage is routing the packet towards the landmark, the 2nd is when it hits a node with the destination in its local cluster (which, in the worst case, is the landmark).
On address sizes, that's a very interesting point about Teredo and 6to4. Yet another reason why IPv6 is too small. :) You should leave a comment on my blog!
If you're interested in this stuff, I'm trying (desperately ;) ) to finish writing up my PhD thesis on (slightly more) practical Cowen Landmark routing. Hopefully done really soon. I havn't considered the issues of source routing for Internet, but that could be very interesting too to consider, along with contrasting it with Cowen Landmark Routing. Designing a network layer to replace IPv6, in case IPv6 should fail at some point, would be interesting too! (Personally, where previously I laughed, now I think ISO OSI was right: addresses should be variable length, indeed maybe the solution is the ISO CLNS protocol ;) ). I can try ping you when I'm done with the thesis if you want. A comment on my blog would be easier for me to find back later. ;)