I'd say the
[id:] and
<a> tags would be sufficient. As for
[node name] and duplicate names, how does the system handle that now? What node does it pick when I click on such a link? For counting references, I'd say if the reference was unambiguous, count it. Otherwise, no.
And yeah, the "vote fairy" could audit all updated nodes once a day and update any reference counts on other nodes. If the vote fairy is already too busy, hire a reference trawl (troll). :)
Multiple references to the same node in one node would count as one reference.
Yes, process all old nodes. Eventually. :) You could do, say, 5000 a day.