This question was solved at http://www.experts-exchange.com/Operating_Systems/Win2000/Q_20695315.html
after points were awarded. Later, alandc came up with an actual solution.
Anything within C:\Documents and Settings (Start Menu, Desktop, etc.) cannot be deleted or right-clicked on without a long delay (about 15 seconds) on this one Workstation. Running NOVELL CLIENT AND Windows 2000 Service Pack 4 on 1.8Ghz PC - have quite a few like this without this problem. Tried updating one from SP2 to SP4 before writing this - it didn't have the problem.
It doesn't matter which profile (subfolder) I choose, nor does it matter whether I am accessing from Windows Explorer, the Desktop or Start Button.
However, icons programmatically applied to the Desktop (My Computer, Network Neighborhood, Microsoft Outlook, Recycle Bin, etc.) do not have this problem.
Ctrl-dragging to copy an icon works at normal rapid speed, but still neither the new nor the old icon responds normally to deletion. The exception is if one of the Icons mentioned above (Recycle Bin, My Computer, etc) is copied, its shortcut will also respond at normal rapid speed.
Opening shortcuts to executables works at normal speed, such as from the Start Menu.