I had this problem with a customer that did a tenant to tenant migration and after the migration users where not able to access our internal SharePoint sites as external users.
luckily I found out how to fix it, here we go!
First go to your Azure AD/office365 user admin page and delete the external users.
Next start a powershell command prompt and connect to Office365. Delete the users from the recycle bin. In my case I want to delete all the users so I just pipe the output to Remote-MsolUser. Before you do this make sure the recycle bin is not full of users that should not be deleted.
Get-MsolUser -ReturnDeletedUsers | Remove-MsolUser -RemoveFromRecycleBin
Next open your sharepoint site. Go to site settings -> people and groups.
The users will still exist here, and if you try to click on a user you will get a delve user not found page. Instead right click on the user and copy the URL.
Now you should see a SharePoint user profile page. Click on “delete user from site collection”
We are almost done. Go to site settings -> access requests and invitations
Click on show history, and right click on the affected users and select delete item.
Go ahead and share the site like you normally but do not select the email of the user in the drop down list. Or you might get an error that says “Sharing failed: the user does not exist or is not unique”