External Domain / Internet Adressing

Hello everybody,

years ago we have created an external Domain and Postoffice, where we created a lot of users, all with a Gateway-Alias for different foreign Domains. Used similar naming (Forename.Surname@xxx.yy)
Now we have run into the Problem described in TID 10101148 : External user receives mail that was addressed to internal domain. Other side is complaining about SPAM delivered to them.
Deleting the Gateway-Alias an using override is not working, it is impossible to choose a differnet Internet addressing, as the external Domain is not seeing the defined Internet Domains.
Any Ideas how this can be solved ?