In OneDrive, a shared document was deleted, yet still shows as a file for all of the people it was shared with. How do we delete this from all shared users?
It will remain until search performs a crawl. If you are on prem you can start a crawl (if you have admin rights). If you are in SharePoint online you need to wait for it to catch your changes.
Check that the file you see has the same path to the file you deleted and are not mistakenly looking at a copy somewhere else.