I finally got the game working in 64-bit Vista. To make it easier for the next person I have uploaded the files which I patched. Here is a step by step method to get the game to work.
1. Copy all the files from disk1 and disk2 into C:\Program Files (x86)\LucasArts\grim\. Some files are the same on both disks so just overwrite any when prompted.
2. I have uploaded some patched files. You can download the zip archive by clicking here
3. Unzip the file archive which you have downloaded and copy the files into C:\Program Files (x86)\LucasArts\grim\GRIMDATA overwriting the existing files.
4. Navigate to C:\Program Files (x86)\LucasArts\grim\GRIMDATA\GRIMFANDANGO.EXE, right click the file and choose properties. On the compatibility tab, select both "run this program as administrator" and also "run this program in compatibility mode for windows 98"
5. Right click on C:\Program Files (x86)\LucasArts\grim\GRIMDATA\GRIMFANDANGO.EXE, and choose "create shortcut". Place the shortcut on your desktop.
6. Run the game at least once by clicking on the shortcut, this will automatically create the registry entries you need.
7. [optional] To play the game without the cd's in the drive, add a new string value into the registry HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\LucasArts Entertainment Company LLC\Grim Fandango\v1.0 good_times=true
8. If you have a nvidia graphic card, then you will need to disable 3d acceleration within the game's options to have clear graphics.
9. Enjoy the game.
Note: There is no need to run the update patch as this is already included in the modified files which I uploaded.
<ADDED> I just finished playing through the entire game and can confirm this game works 100% using the method I gave above.