Did this change recently? I had no problem paying with my German Maestro/EC for everything a couple of years ago. (Just like in most European countries, really)
Maestro is a different animal. I only have Visa/MC and I had to carry cash. Two examples were a random restaurant in a mall and a random tiny cigarette shop. At the latter they told me Visa can cost like 10%.