- The Computer option in the Start Menu
- The Taskbar
- Any File or folder
After a bit of research and trial and error it turns out this is due to one or more corrupt Context Menu Handlers also known as Shortcut Menu Handlers that handle things like "Send this File to a Zip" or "Open With".
You can delete these entries one at a time after backing up the registry but it turned out to be caused by a different entry every time.
You will have to delete the entries using regedit under:
Perhaps it's poor troubleshooting technique but I ended up just deleting every entry under ContextMenuHandlers to save time and no users have every complained. Always do a backup of the ContextMenu Handlers in both locations, of course.
No reboot is required after the deletions - you'll find explorer works as intended.