We are experiencing the same behaviour as C_the_S now across all our tenants now too!
It appears this new behaviour described by StephenRice has been possibly rolled out in a broken state. We can consitently recreate this failure with any new user on their first invite.
We've opened a ticket on this with no response yet.
If any of our users share with the Specific User to another user with a work or school account in another tenant and that user is already logged into their browser, they are doomed to have a broken link forever.
They receive the invite email, click the link, get the email verification code and then after entering get another screen telling them to "login to get access immediately" but with only a Next button. As soon as they click Next they receive access denied, and no order of logging in our out of SharePoint or clearing cookies will solve the issue.
We do notice the #EXT# account is added into their sending tenant.
If the original user then sends a new invite on the exact same document or folder with the Specific User and now picks the user that was auto-added as an #EXT# user, then the complete process works normally.
This is a terrible experience for users and we're getting widespread complaints on what used to work well.
It seems that whatever is happening in the back end between this verification code (and whatever method that uses to access the sharing) and the #EXT# user getting added completely breaks the permissions on the original file/library/site.