I had a strange issue recently where Microsoft Word was unable to open files from the Recent Files screen. The files were there, e.g. sitting on the Desktop, and going to File > Open worked, as did double-clicking on the file, however if you wanted to use Recent Files to open them, it said that the file had been moved or deleted.
Luckily the fix is pretty easy. First quit Word and then, there’s a .plist file in the Word container. Go to ~/Library/Containers/Microsoft Word (or ~/Library/Containers/com.microsoft.Word) and then in there go to Data/Library/Preferences.
In this folder will be some .plist files, find and trash the com.microsoft.Word.securebookmarks.plist file.
Finally, launch Word and this functionality should be restored.