@Bistro ,
When you remove the permission of the user in site, he has no access to the site again.
Since the user browses to this site before, his user information is cached in UserInfo list of the root Site Collection.
This is why the user still appears in people searches and in the SharePoint Online Management Shell when you use the Get-SPOUser cmdlet.
If the user is still active in your organization, there is no need to remove it from the UserInfo list.
If the user has been deleted in Microsoft 365 admin center, to avoid confusion when people view the people picker, we could remove deleted users from SharePoint UserInfo list, for more information, please refer to:
https://learn.microsoft.com/en-us/sharepoint/remove-users#remove-people-from-the-userinfo-list
If an Answer is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.