The following worked for me!
Tried all of the previous answers, but none worked.
Then I came across a fix described here on Apple Forums.
The first solution did not work, but the second one did.
The description there is very clear, so I won't even try to summarize. Just follow the link. Hopefully it will help others too.
FYI: All my recent items were gone in all apps, in Apple menu the whole menu item was even gone, and changing in System Preferences from none to whatever kept reverting back to none.
I am on a MacBook Air (early 2014), running El Capitan 10.11.3