Newspapers are down in the dumps. But they remain powerful forces in local. Accordingly, the search engines (Yahoo, Google and Microsoft) are now beginning to fight for partnerships with newspaper sales channels, which they see as one of the best ways to reach into large local advertisers, and a good way to geotarget display ads.

Today, Microsoft fired a shot across the bow by announcing a wide-ranging search and display pact with Advance Internet for the 36 Advance Newspaper titles. Advance is part of the multimedia conglomerate that also owns Conde Nast magazines. The deal echoes the services provided by the Yahoo Newspaper Consortium, but allows Advance to use its own ad server.

Major components include behavioral targeting, geographic targeting and the opportunity to add local eyeballs via exposure to the broader Microsoft Media Network, which has a 76 percent reach among U.S. Internet users, and includes MSN, MSNBC.com (which today bought EveryBlock.com), CNBC and Fox Sports. Microsoft will also be able to sell text ads and display ads to Advance Newspaper sites.

The deal enables Advance’s sites to define broader geographic markets than the circulation areas of its 36 separate newspapers — a limitation of the Yahoo Consortium in certain markets. Advance’s sites tend to cluster on a regional and state-wide basis and include NJ.com, Al.com, Cleveland.com, MLive.com, NOLA.com, OregonLive.com, SILive.com, Syracuse.com, MassLive.com, PennLive.com, Gulflive.com and lehighvalleylive.com.

The MS/Advance pact has been cooking up for several months, well before Microsoft’s Bing became the default search engine for all Yahoo sales — including local business sales of the Yahoo newspaper consortium. Microsoft might like it more because it doesn’t give such a huge chunk of certain advertising (88 percent) to Yahoo.

We don’t know, however, whether the deal has been entirely sorted out within Microsoft. Some internal political issues might arise, especially if it is deemed to compromise the much more important relationship with Yahoo. We shall see.

As it is, the deal isn’t exclusive to Advance. It could be replicated with other local media companies — although obviously not to the members of the Yahoo Consortium, which are locked up for several years.

In fact, there aren’t that many major newspaper companies left unsigned. But Gannett, with 86 U.S. papers, and Tribune are obvious targets, as Ken Doctor points out in his analysis. The deal may also affect smaller newspapers, and other local media, such as Yellow Pages, broadcasters and cable TV. Microsoft already has some relationship with Yellowpages.com.

Advance Internet President Peter Weinberger sees the deal as a “re-messaging opportunity. We are already known for our quality audience and for our trusted relationships with our accounts,” he tells us. While Advance is something of a secretive organization and rarely toots its own horn in public forums, Weinberger emphasizes that the company has got to be considered a big win.

“We have the No. 1 news and information sites in each of our markets,” he says. “Five of our sites rank in the top 10 of newspaper affiliated sites based on local penetration of adults 18+.”

The Advance/MS offering has already been pre-sold on a test basis to certain advertisers, including those in core newspaper categories such as auto dealers, financial services and local retailers. Travel is another potentially lucrative category.

“We’ve had a positive response so far,” says Weinberger. “It should take a couple of months to settle down,” and will really prove itself in 2010.

In the meantime, “We are achieving our goal to put together a digital marketing plan based on a conversation with our clients,” adds Weinberger. “We want to meet the objectives of each of our advertisers with our campaigns on our site.”

Weinberger especially sees a lot of promise for his local advertisers with search — possibly extending beyond core newspaper advertisers. “Many [advertisers] are interested in search, but it is relatively complex,” says Weinberger. “We say: ‘Let us take on the burden of managing this for you.’ … We show them the value associated with SEM,” in context with the broader advertising purchase.

While Microsoft is certainly competing with Yahoo by making the deal, Advance’s involvement should not be taken as a slap against the Yahoo Consortium, says Weinberger. “I have heard a lot of positive things” about the Consortium, he says.

But “Microsoft makes more sense at this time. It allows us to use our current ad server platform [24/7 RealMedia].” The situation is the same with Google, which would presumably mandate use of its DoubleClick division.

An added benefit of the deal is the consultative relationship that is promised by Microsoft.  “Microsoft understands that we are experts in the local field,” says Weinberger. Accordingly, Advance is being consulted on the beta development of Microsoft’s PubCenter, which provides text ads for display on Web pages, with a wide variety of design and reporting features.

Meanwhile, Microsoft says it is pleased with the deal. “The local perspective is important to us and will be incredibly helpful as we build out our reseller efforts,” notes Microsoft PubCenter GM Brian Handly, via e-mail. “This collaboration with Advance Internet presents a good opportunity for us to tap into newspapers and other local media companies.”

Regarding the impact on the Yahoo Newspaper Consortium, Handly says: “It is too soon to discuss specifics of the Microsoft-Yahoo deal and what impact this may have on Yahoo’s newspaper consortium. Right now our focus is building a great No. 2 player in search that creates choice, value, and innovation for consumers and advertisers.”