Thanks for your answers so far.
Unfortunately, I don't have any time to try some of the suggested solutions ATM.
The problem, however, doesn't seem to be restricted to using shell extensions/the context menu, as I've had Locate32 crash on triggering a simple search or double-clicking a search result as well.
I might try the latest version, but again, I don't have any time at hand to tackle the problem right now.
Another thing that might be related to these problems is that XP has been flakey for me for some time now, mostly resulting in weird UI problems.