Nick,
As a test, create a new user account to see if the Start Menu jump lists work properly in it. You can pin Notepad to the Start Menu to test with and open some text files to see if they show up later.
If it does, then it may be easier to just create new accounts for the affected user profiles. Afterwards, copy all of the contents of the old user account's
C:\Users\(user-name) folders (including
hidden AppData folder) into the corresponding new account's
C:\Users\(user-name) folder. After everything checks out ok, you can delete the old user account while logged in the new user account.
Other options to try and fix this would be: