In Germany the acceptance for credit cards only became large scale after the interchange fee was limited. Today, most stores that accept card payments also accept credit cards, but only MasterCard and Visa. Using an AMEX as your primary card would be a pretty bad experience, because you'd constantly need a backup.
With that said, I'm happy most merchants don't put up with the humongous fees—in the end the prices are just raised to compensate for them.
Same in NZ. People who work for more... insular... American companies here are regularly embarrassed by being unable to use their corporate card (because e.g. IBM mandate Amex) most of the places they go.
