You are experiencing why installing program files in the designated program files directory is not just a symantical issue. Non-portable programs are referenced all throughout the system and usually break when subjected to simple file operations, or in this case, to the disappearence of the entire drive. In theory, the program files entry could be altered, but a lot of software is not build to survive this. The only viable way to move installed programs to a new drive is to uninstall them properly, then reinstall them elsewhere.
Needless to say, reformatting the drive is not equivalent to a proper uninstall procedure and with the program files missing altogether, chances of a clean and succesful uninstall are abysmal. If possible, your best bet would be to recreate the original G:-drive from backups and to remove the installed software appropriately.
Option two is to manually remove all of the remaining references to programs that were once installed on the G:-drive. A tedious task for a single program that could have left its mark in dozens of registry keys, user-space files, dependencies, third party software... For many programs, as probable in this case, this is impossible. At best, it can serve as a quick and dirty solution to patch specific problems such as the install errors for cilk++. Be prepared to continue to work with a very unstable system.
The most rigorous, but quite likely fastest and best way to resolve the situation is to backup all valuable data, format the C:-drive and reinstall the operating system and other installed software.