Angels have the Phone Box
Well, I thought that those all fell under the "jump lists" category, but perhaps you could try going to the Applications tab and selecting the box for Office, and clearing out things that way.
So, you ran Ccleaner, re-pinned Excel to the taskbar, right-clicked the Excel icon, selected a file, and it still only opened up Excel and not that particular file? Try again - unpin, run Ccleaner with the Office box selected under Applications, reboot, re-pin Excel, and see if any jump list shows when right-clicking.
Very strange. What version Office are you using? Can you reproduce the same problem with Word? I know you don't use that much, but it would be interesting to know if it's an "Office" thing, or an "Excel" thing.