I should stress that the problem has occurred consistently over multiple attempts over a week and on two tenants. Also, there's never an appearance of a problem when actually doing it, just later when you look into it because you're wondering why no one has access to the app (except me). Then you see the audit log and realize a definite problem.
I'm global admin.
The app (called Adobe Document Cloud, which is the one on the left):
https://documentcloud.adobe.com/o365pdf/start.html
The addition of the app works, but the "Deploy to all users" step (Adobe's terminology) ultimately does not, even though it appears to work at the time, and even when allowing 48 hours. That step is the same thing as going to Azure AD, Adobe Document Cloud, Permissions and selecting "Grant admin consent" (for company). It all looks normal to me there:
https://i.imgur.com/CnE9M2y.png
And it agrees with what was asked in the consent:
https://i.imgur.com/5l4pzgI.png
The error in the audit log (happens every time):
Activity Type: Add app role assignment grant to user
Category: UserManagement
Status: failure
Status reason: Microsoft.Online.DirectoryServices.UniqueKeyPropertyException
User-Agent: EvoSTS