Martin Belam has written an interesting series of posts on internal vs external linking on the Guardian's website. His latest one summarises some of the comments and discussion that have taken place around the topic. Internal vs external links is one of those evergreen web debates (along with whether said links should open in a new window or not), but things do seem to be moving on a little.
I was about to weigh in with some of my thoughts on the subject as a comment on Martin's blog, but decided to post it here instead.
I like the idea of doing what's "least surprising". It's interesting if you compare this on news websites to Wikipedia though. On Wikipedia, there's a general expectation (I think), that all links lead to internal pages - even if they're a company name like "Microsoft". This is probably down to it being an encyclopaedia, which is necessarily "meta" - it's almost like an alternative web, where instead of linking to the thing, you link to a page about the thing.
Interestingly, Wikipedia uses a fairly decent mini icon which is used inline after links to denote external links. I'm not sure how intuitive this is to a first-time reader (though it has to be more obvious than using colours), but once you've understood it, it seems to work without being intrusive into the reading experience.
There's an interesting factor that humans make when deciding where to add links, which I wonder whether your auto-linking tool takes into account. That is, humans are unlikely to link well understood terms, like "Microsoft", "David Cameron" or "France", as there's not much value to be gained from those, as most readers are going to already know who and what they are. Linking has a much greater value when the subjects are things that some portion of the audience are unlikely to have heard of (if it's likely that no-one's heard of the subject, then you'd hope that it'd be explained in the text itself).
This idea sounded like it could be graphed. So here's a very crude diagram by way of an attempt at illustration:
What do you think?