Unable to start certain .exe applications error (0xc0150004)

I have been running into this problem for some weeks now and thought it's time to seek additional help. Initially, i was unable to launch .exe applications that relied on the MSI installer...so i searched for a solution...the solution was to got to services and start the 'windows installer service'...doing this fixed some of the issues but apparently not all of them. I still can't run Fireworks or AvastUI.exe and other apps such as Upgrade Advisor. Heck, i can't even run certain windows updates. I have a HP desktop running Windows 7 x64 Home Premium. I know for a fact that there are no mal/ad/spyware on my computer...I have ran Trojan Remover and removed all the junk that i'm sure caused the problem in the first place. Here are some windows provided solutions i have tried: I have ran all MS 'Fix-It' apps, uninstalled reinstalled my apps, went to command line ran 'msiexec /regserver'. I know windows installer is installed but its corrupted for sure. Any solution/suggestions are welcome...my last resort is to wipe out the OS and reinstall it. I hope this is the right forum to post this in...if not, please let me know.

Have you tried sfc /scannow from an elevated command prompt?

I've just tried it and received the following:
"Beginning verification phase of system scan. Verification 95% complete.
Windows Resource Protection found corrupt files but was unable to fix some of them.
Details are included in the CBS.Log windir\Logs\CBS\CBS.log. For example
C:\Windows\Logs\CBS\CBS.log"

Thanks for the prompt reply Sibbil, it's much appreciated. I ran this command twice with the same result.

I would try running two more times. It can take multiple runs to fix all issues. If that doesn't work consider a system restore to a date/time that precedes the date/time the problem first appeared.

I'll do that. Thanks for the help :)

Let us know how it goes!