I have this problem also.
I am on my third, faulty, installation of Google Desktop Search V3. The first time around, I have forgotten. Last time, I got the "Google Desktop Search Did Not Start Up Correctly" message, tho I could not start it via the Start menu.
On this third installation it simply does not start properly. No error message this time. When I click on its icon on my desktop or via Start Button, my computer makes the sounds for opening a program, then closing a program, all in half a second.
I can start Google Desktop by finding it (two entries, I find) under the Processes tab in Windows Task Manager (ctrl+alt+delete) and clicking on End Process. THEN it will start by clicking its shortcut icon or via the Start Button.
If it keeps on like this I will stop it starting with Windows, and start it myself...