Interestingly, the recently opened documents are appearing in the dock icon when I right-click (automatically) - and I can successfully open them from there, so I am baffled why the Open Recent menu is not working.
edit: I notice though that the recent documents in the dock icon do not update - when I open a document and close it. I see the following error in the console:
Insert failed for list identifier com.apple.LSSharedFileList.RecentDocuments Error: Error Domain=NSPOSIXErrorDomain Code=1 "Operation not permitted" (Restricted by sandbox) UserInfo={NSDebugDescription=Restricted by sandbox}
but I don't see any sandbox entitlements that control this.