Media Files Not Being Removed After Deletion

Tl;dr: WordPress does not seem to be removing media when it is deleted via the delete permanently feature in the media library. Does anyone have a solution for this?

I added a PDF to our site and linked to it from a page. Later, I discovered it had a blank page at the back of the PDF so I deleted the file and uploaded a new version under the same name (to be lazy and avoid changing the link ?? ). When I clicked the link the old PDF showed up up instead of the updated one.

Confused, I deleted the pdf altogether (by clicking Delete Permanently in the media library), refreshed the page and clicked the link. It still worked! I checked in private browsing and a completely new browser I had not used since downloading it. The link worked and it clearly isn’t because it is cached.

The only explanation I have is that WordPress is not taking down media after you delete it. Does anyone else know of another cause or a workaround to get wordpress to actually remove the media file?

Thanks!