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.