It turned out the user had installed some Norton/Symantec app that had its own recycle bin. We had to head to Symantec for a removal tool.

There can be other apps that intercept the file but there is that one other problem Microsoft appears to have not cured after many years. Ready?

If the file is over 4GB in size, it will never go to the recycle bin. No fix is known and it appears Microsoft is not going to work on that one.