One of my clients had an issue with a Windows XP machine attempting to synchronize off-line files with a server that no longer existed on the network. I followed the instructions in the following KB article to reset the off-line files cache.
After the reset, right-clicking on a file to bring up the options menu took an EASY 30 seconds. Double-clicking on a Word, Excel, PDF, or any other file took 45 seconds to open the file. However, if one opened Word first then used the Word File Menu to open the file, the operation was instantaneous as it should be.
After an entire night of Googling, Digging, and MSN'ing, I found two solutions to this problem:
We used to have a couple of little utilities that ran straight from a share, one of which was the popular IrfanView image manipulation software. Whenever the server was switched off, if some users right-clicked on any file in Explorer, there would be about a 30-90 second delay before the context menu popped up. I thought there was something wrong with DNS and all sorts of things but in the end I tracked it down to being the fact that IrfanView adds in some items to the context menu ("Open with IrfanView" IIRC) which must've been pointing to the EXE file on the shared folder. Looking back, not everyone used IrfanView and it was only people that DID use it that were having the problem. In the end I went through the registry and found all references to IrfanView. These were deleted and hey presto, the problem went.