Welcome to the wonderful world of the New York Times News Service! They usually charge based on the circulation of the subscribing paper. To their credit, they also aggregate and send out tons of stuff from lots of other papers around the country.
Of course, the Times itself owns a number of papers around the nation itself; I would presume they get access for free.
Also, I'm curious about the headlines over a NYT's article -- does the NYT retain any control over the content of the headers?
I seriously doubt it. Most wire services simply sell their data, and leave the individual subscribers to use as much or as little of it as they want.
And wire service articles get altered by the local paper every day. For example, look at an AP article in your local paper's sports section about some NFL team. It'll probably have a line or two somewhere in the middle saying something like "Joe Blow, the former star quarterback at [obscure local college]...." That wasn't in the AP article; the local sports editor shoved it in there to give it a bit more of a "local" feel.
Even better, wait until some really big story happens in your local paper's coverage area, and look for articles on that story with AP bylines. Those stories are usually massively altered by the local paper's reporters to include as much local info as possible, and sometimes just to crow. If there's a sentence in there that starts off, "This latest piece of important evidence, first discovered by the Orange County Register three days ago..." you can bet the house the AP didn't send out the story like that.