It happens every time I log out and log back in, or reboot.
After some debugging, I figured there is a FencesShellExt entry in the registry causing the problem.
HKLM\Software\Classes\Directory\Background\ShellEx\ContextMenuHandlers
After I remove this entry and log in again, the problem is gone.
I left other FencesShellExt entries unchanged, including HKLM\Software\Classes\Directory\ShellEx\ContextMenuHandlers
I don't know if the registry key I deleted is important or what purpose it serves, maybe this could be a question for your developers...