Sorry for digging up this older post, but I just wanted to add some information.

In general, there are two major competing debit card schemes in Germany: Girocard and Maestro. They are both being touted as the successors to the EC-Card, with the latter term still in general usage today.
Girocard is vastly more accepted by merchants in Germany than Maestro as the transaction fees are significantly lower. Some shops (such as Aldi-Nord, iirc) have terminals that accept both, but officially advertise only Girocard as available payment option. Most shops just plainly state "EC-Karte" (even when asked specifically if Maestro and/or Girocard) and leave it up to you to try if your Maestro card gets processed or not.

From several conversations with shopkeepers I can indeed confirm the reluctance to accept CCs and Maestro is due to the transaction costs involved for the shops, which they tend to minimize by focusing solely on Girocard, or not offering plastic payment options at all. Pretty much unpredictable, even though the rule of thumb is the pricier the store the more likely you can use your Maestro or CC there. Girocard is by all means your best bet.

PS It is true many people in Germany seem to distrust any form of money or investment that is not "physical" in nature, but ask these folks where they get their "hard" cash from and you're left with a baffling "I draw it from my bank's ATM. Why?"

Anyway, just my two Cents...