The Problem Just "Went Away"?
This is interesting. After not using Parallels for a couple of years & instead using Boot Camp to reboot into my WinXP partition on my MBP the times I needed Windows, I took advantage of an upgrade offer & purchased Parallels 5 a couple days ago. I installed it and tried to run Desktop, experiencing the exact same problems as described in this thread (I didn't ever actual get it to come up - not having the patience, I force quit it each time I tried to get it to run after watching the Dock icon bounce over and over and over).
Then I found this thread & contemplated asking Nova for my money back or waiting it out for the fix. As I considered my options, I decided to replace WinXP with Vista in my Boot Camp partition (temporarily until Apple releases Boot Camp drivers for Win7). I went ahead and deleted my WinXP Boot Camp partition so I could recreate it a little bigger. On the recreation attempt in Boot Camp Assistant, I got an error stating that the partition could not be created due to some operating system files that were unable to be moved. I did some research, discovered this was a common problem when deleting & recreating a Boot Camp partition, and that the solution was to image the system disk to an external FW drive, reboot from it, delete, recreate & format the partition on the system disk, restore from the external FW drive, reboot from the system disk, and finally create the Boot Camp partition.
I did exactly that using a utility called SuperDuper and it worked flawlessly (and took about 4 - 5 hours). So, I then installed Vista Ultimate on the new Boot Camp partition. After that was up & running, I rebooted back into OS X intending to start Parallels Desktop, waiting out the long time it took to get up & running, create a new VM from my new Vista Boot Camp partition after it was finally running, and then take the steps outlined above by Spencerian to exclude my new VM from Spotlight as a temporary fix. Much to my surprise, however, when I double-clicked on the Parallels Desktop icon, it came up immediately, asking for my activation key! I entered it, and was able to create a new VM right away from my new Vista Boot Camp partition. And, the VM runs Vista flawlessly. All without making any Spotlight changes.
So, I don't know what happened that solved the problem - all I can think of was the imaging of my system disk then recreating & restoring it rebuilt some Spotlight indexes or something. I know this is a pretty dramatic "solution" to the problem, but if any one else wants to try it, you can download SuperDuper here:
http://www.shirt-pocket.com/ & you do not have to purchase a $28 license to do a basic backup / restore as I described (it is a great, easy to use backup / restore utility, however, & I encourage anyone who finds it useful to purchase a license).
Tom