One of the guys mentioned in these forums that uninstalling Google Desktop did the trick to get Demigod to launch. In particular, it's the following dll loaded in the registry upon Windows startup:
"Appinit_Dlls"="AVGRSSTX.DLL WBSYS.DLL C:\\PROGRA~1\\GOOGLE\\GOOGLE~1\\GOEC62~1.DLL"
Notice how this registry key can contain multiple DLLs for different applications, all within the same reg value, separated by spaces. On my system, the first DLL belongs to AVG antivuris, the second to WindowBlinds, and the third to Google Desktop.
By removing the reference to the Google DLL (i.e. the highlighted part above) and rebooting, Demigod launches 100% of the time. That basically means I have to edit the registry, remove the DLL reference, and reboot to play Demigod. When I'm done, I have to add it back in and reboot so Google Desktop works again. While this is inconvenient, it's better than permanently uninstalling Google Desktop, which I happen to like.
This actually isn't bad for me, because I have a special gaming configuration (a set of reg files) that I run then reboot before playing heavy games anyway.