- ID-linking: Each node already has a unique identifier, so why not use it? The problem is that nobody remembers node_id's, and it can be difficult to find the id of a particular node. Perhaps if this were made available somewhere on every node (inconspicuously, of course... maybe only readable if you select it?).
- Parent Linking: This is just generally good practice when appropriate, but I don't think is solves the underlying problem. There are times when you want to refer to a particular reply, and other, more exact methods would be useful
- Title Dirtying: Ack, this reminds me of the garbage C compilers tack on to variables before linking ;-). This may work, but it requires consistency and a fair amount of work. Node id's are a better source of uniqueness, IMO.
- Search Linking: I think this would reduce, rather than eliminate the existing problem we have with name conflicts where the engine returns too many results to be useful. You would get fewer hits than by specifying title alone, but in the worst case, still more than the one you wanted. Besides, a real search facility like you mention and I've lobbied for before would be much more useful generally.
- Special Thread Linking: This is fairly interesting, though 8 digits might be a bit of overkill: I doubt any node will ever have a billion replies :-). The packing could work on both server- and user-sides, but it might confuse some people. But then, Monks willing to go that far out of their way for a link could undoubtedly figure it out. Alternatively, each reply could be given a (possibly sequential) identifier unique only within the thread. So, the first reply would have a thread_id of 1, second 2, etc., regardless of depth. Of course, these numbers wouldn't be in order when displayed, but as long as they were on the node somewhere that wouldn't matter. This, too, would need a special link mechanism like the thread:n:m:... system you propose.
When the day is over, I would prefer to just extend the existing id system, which guarantees uniqueness but doesn't expose itself sufficiently to users wanting to fully utilize it. And like I've said here and before, a good searching facility would be immensely helpful for this purpose and others.