About your first question a brief intro:
Microsoft Setup Installer (MSI) is more like an intelligent installer. It's certainly not easy to convert an EXE to MSI but it's not that tough as well. Typically MSI installers are used for application deployment / installation on large scale.
It's interesting that MS Windows Malicious Software Removal Tool removed all .exe files from your computer ... believe me ur machine wouldn't work if it does
Converting those .exe's to MSI wouldn't solve ur purpose here bcz the tool would delete any MSI as well if it's infectious.... but if it's deleting any exe that falls in it's eye ... thats trouble ...
Abt your second question no i guess / infact hope that Virus scanners can scan within zipped files even if they'r password protected. But can't say definitively.
But from all this ur PC does seems to be in some deep trouble so do a thorough virus scan on your machine ... get some malware detection software and scan ur PC with that ,,, nd then run hijackthis on your machine and post the logs here ...
Best of Luck