issue is its online 365 so it wont be easy and you wont like the answer.
You have to make sure its on sharepoint side that the user still exists....
within sharepoint goto the webapplication site collection root site to see all users within the site.
access the User Information list by adding
/_catalogs/users/simple.aspx ... e.g.
check to see if the user still exists there? if not than the user would be within your domain users usually within active directory.
as this is 365 the following is not possible:
if this was on premis than you have better options of going to central admin and running schecheduled timer jobs. When you call the service or any function that removes a web/site/sitecollection/ and/or users than it usual create a timer job service to be scheduled. If you were to have access to central admin you could go into timer shedules to check all jobs and locate the timer job and select it to run now. That would update sharepoint with the content database to reflect changes made. I think its User Profile Synchronization service timer job that will run against the content database with deleted users within the User Profile Synchronization service application deleted list.
so you could run the service again within central admin or make that timerjob run now rather than later. But this is all a presumption that the user has been deleted from the hidden list noted above and if still shown means that the user is within active directory.
timer jobs (does not apply to 365)
how to properly remove users profiles
similar method to on premis method but for 365:
use the managment shell! this will work instantly:
Remove-SPOUser -Site https://contoso.sharepoint.com/sites/sc1 -LoginName firstname.lastname@example.org -Group "SC1 Owners"
This example removes a user who has the email address
email@example.com from the group SC1 Owners in the site collection
but your limmited and the above will fail, why? becasue you need to be at site collection admin level and global admin level for it to work which according to you, you are not!
so you are only left with this option that puts you back to square one! and would mean you have to wait till the retention policy is over for the timer job to kick in!
sign in to the Office 365 admin center with your SharePoint Online administrator username and password
Choose Admin > SharePoint. You’re now in the SharePoint Online admin center.
Choose User Profiles.
Under People, choose Manage User Properties.
On the Manage Profile Properties page, in the Property Name column, select the profile property that you want to remove, and then click Delete.
Note If the Delete command is grayed out, the property you are trying to delete is a default property in SharePoint Online and it cannot be deleted.
In the dialog box, verify that you have selected the correct profile property, and then click OK.