This error can also occur when a user is prevented from consenting to an application due to Microsoft detecting that the permissions request is risky. In this case, an audit event will also be logged with a Category of "ApplicationManagement", Activity Type of "Consent to application" and Status Reason of "Risky application detected". That might be a reason for it to succeed on the retry.
Other possibilities are that there was a permission change or a delay between data centers.
Do you get any audit events or additional errors?
I would recommend visiting the troubleshooting guide for more clues.
Without having insight into your tenant, we may need to open a support case for this. I am leaving details for how to claim this option in a private comment for you.