While it's not a definite answer - someone at work had a similar issue with context menus last week. When you right click on stuff there is a flurry of registry activity.
He figured it out in the end by using
Sysinternal's Regmon tool. He then searched the output for '\\'. It turned out that a program had been registered in HKeyClassesRoot that referred to a UNC path (\\server\share\dir\app.exe), in this case the machine was unavailable. It may also choke for longer on paths to exe's that no longer exist. (e.g. something being deleted without being unregistered)
Take precautions of setting a system restore point before you muck w/ the registry (just in case). Figure out the Regmon filtering otherwise you can easily 'flood' your system with registry events. You'll need to watch for 'explorer.exe' process events only.
Worth a thought anyway.