I have the exact same problem. I have found that it is only slow opening the dialog box when right-clicking on a shortcut. If I R-Click on a file or program, the box opens instantly. I am using Win 2k-Pro, build 2195: SP4. Active desktop, effects, on or off doesn't make a difference. It also doesn't seem to matter where the shortcut is or where it is pointing to. Selecting the shortcut, then right-clicking doesn't make a difference either.
Any suggestions?