You're right, the recent items (Documents) list is completely maintained by Windows, it is only shown by Classic Shell.
On Windows 7, open Taskbar Properties and go to Start Menu tab and turn on jumplists by checking the option "Store and display recently opened items in Jump Lists". Also, make sure, the "Number of recent items to display in Jump Lists" is not 0. After enabling it, the history will start getting maintained for documents opened after that.
On Windows 10, go to the Settings app (press Win key+i) > Personalization > Start and turn on "Show recently opened items in Jump Lists on Start or the taskbar".
Additionally, one tweak you can do is add or hide specific file types from the recent list using a third party app called NirSoft FileTypesMan which tweaks the registry:
http://www.officehackery.com/2009/11/hi ... ndows.html If "Don't add this file type to Recent Documents" is checked for an extension in FileTypesMan, it won't be added by Windows even if you open it. So for those file extensions which don't show up in the Recent list, check them using FileTypesMan and uncheck that option.