IANAL but trying to read the law, it seems to be a rather blatant lex google.[1] They specifically state "search engine or similar services" should be prohibited from (in an extreme interpretation) linking to newspapers, if they do not pay. ( The rest of the law is probably just redundant, since it seems to reimplement copyright for a small subset of already copyrighted material.)
Google should state a new policy. We're not going to spend our money on servers and bandwidth indexing and linking to German publishers who won't pay - I guarantee you the value of the traffic they get from Google dwarfs what Google gets back from them in terms of marginal revenue directly attributable to their content. That's the thing about Google. They make tons of money - but given that they're a prime mover of traffic around the Internet they make a damn site more money for other folks - including newspapers.
So Google should charge. Then they can do like the phone companies with termination fees and call it a wash.
[1]http://dip.bundestag.de/btd/17/114/1711470.pdf (German)
[EDIT: spelling]