Thanks
@bogdanw, I tried this - I had to give full disk access to the Terminal app first but then it worked. I checked, I had 51 files in the Trash. I did this, logged out/in, and interestingly I had 39 then. But I still couldn't put back any file.
So I did an Empty Trash, then deleted a new file (screen capture, file on the desktop). With only the 1 file in Trash, it failed too - "Doesn't exist anymore".
So then, I dragged the file from Trash to my documents. I then deleted the file from my Documents folder. Put Back worked!
So then I moved the file from Documents back to Desktop, and same error - "Doesn't exist anymore". So the problem may be just deleting files into Trash from the Desktop! Does this sound like some sort of permission problem? I never fool with permissions, is there anything I should check or verify? Does this sound like something else that may be the culprit?