What you have found here regarding direct debit is called IBAN discrimination and is against the law. Specifically, against article 9 of EU Regulation 260/2012:
- A payer making a credit transfer to a payee holding a payment account located within the Union shall not specify the Member State in which that payment account is to be located, provided that the payment account is reachable in accordance with Article 3.
- A payee accepting a credit transfer or using a direct debit to collect funds from a payer holding a payment account located within the Union shall not specify the Member State in which that payment account is to be located, provided that the payment account is reachable in accordance with Article 3.
The relevant German authorities are aware of it but the mills of bureaucracy grind slowly as we say in German. Unfortunately, even many public institutions like the collector of the broadcast fee and health funds practice this.
You should direct your complaints to the relevant supervisory body if there is one. For Amex, that's BaFin which is aware of this problem and known to take it seriously. For Vodafone, complaints can go to any customer protection association, such as a Verbraucherzentrale but I don't know if they do anything with such complaints.
For the bank card in shops, no store is required to accept any card and some (especially smaller ones) only take ones badged with the German Girocard system.