I think I found the solution or atleast the reason why this problem persists.
A user from sevenforums.com had a great explanation and possible fix for this issue.
It's all related to the cursed Windows Game Explorer program. Here's the quote of that user:
"I had this problem, too. Older games, like NOLF, NOLF2, Painkiller, Deus Ex suddenly wouldn't start. The game would hang and when I checked the task manager, the game would be in the list, along with a Rundll32.exe child process that was hogging up CPU resources. I recommend using Process Explorer, instead of the default task manager. It shows the relationships between the game and any child processes a lot better. One of the libraries that RunDLL32.exe was loading was gameux.dll This file turned out to be what was causing the hang. Because it's a system file, the trick was finding a way to take ownership of the file, so I could disable it.
This worked for me on Windows 7 64bit.
First, Create a Restore Point, in case you mess something up.
Start the computer in Safe Mode.
Use Windows Explorer to navigate to your C:\Windows\SysWOW64 directory.
Look for gameux.dll. Right-click on it and bring up the Property sheet.
Click the 'Security' tab. Take ownership of the file by copying its permission from whatever account had full access originally. On my computer, that Owner was called "TrustedInstaller" You need to transfer ownership to whatever your default Administrator account is called.
Now you can rename the gameux.dll file to something like gameuxBAK.dll (It's good practice not to delete possibly-critical files in case you need to restore them, later)
(There is also a copy of gameux.dll in the C:\Windows\System32 directory. You may need to rename that one, too.
Reboot normally. The games should launch now.
My theory for why this works is that when the older games were installed, they were registered with the Windows Game folder, which tries to download updates and game icons whenever you launch the game. Microsoft is phasing out support of Windows 7 next year and in typical Microsoft fashion, they started removing the online support early. I think the RunDLL32.exe is trying and failing to contact the online resources for game updates. When it fails, instead of handing off control back to the game, it tries to endlessly contact Microsoft for resources that no longer exist."