Just thought id share my experience with this game on trying to run it on XP.
So far I was having no luck at all getting it to work, when playing it would just freeze up randomly and the cutscenes would stutter and the sound would play up.
I tried the patch, no work, i tried cpukiller(which is useless with the 20minute trial), I tried shutting down any program that might be affecting it, I even turned off Hyper Threading in bios, nothing worked.
Solution - once installed right click on the shortcut for grim fandango on your desktop, click on properties, then click on compatability and select it to run in windows 98/windows me.
Problem solved !