msi.dll is component that contains functions used to install Microsoft Installer packages. You can download Windows Installer from here
Registry cleaners are extremely powerful applications. There are a number of them available and some are more safe than others. Keep in mind that no two registry cleaners work entirely the way. Each vendor uses different criteria as to what constitutes a "bad" entry. One cleaner may find entries on your system that will not cause a problem when removed, another may not find the same entries, and still another may want to remove an entries required for a program to work. Unless you have a particular problem that requires a registry edit to correct it, I would suggest you leave the registry alone. Using registry cleaning tools unnecessarily or incorrectly can have disastrous effects on a system.
Can you be more specific as to why you cannot run your anti-virus in safe mode?
After rebooting into safe mode, when you are at the logon prompt, make sure you log in as the same user account
which you used to download/install the program. If not, you may not be able to find it.