It’s important to note that the wording of the error may differ, but the root error (All Aliases Have Failed) will be the same.
To resolve this, please ensure all gateway servers in the service provider infrastructure can communicate with the tenant(s) repository and the Service Provider's Veeam Server.
For communication route, reference:
As a note, private gateways are not recommended and are one of the more common scenarios to encounter ‘All Aliases Have Failed’. Veeam will attempt to load balance across all available gateways based on current tenant connections, and a gateway usable by a specific tenant can get selected, resulting in this error. In addition, a private gateway can introduce a 4-minute and 15-second delay on every task (disk) a tenant processes.