[Note: Eventually I got a hint from Karel Zikmund on this thread, which helped me solve the mystery. I'll paste my reply here - for the greater good].
So, I used the following line to sign-upon-import the assembly:
tlbimp C:\WINDOWS\system32\msi.dll /out:Interop.WindowsInstaller.dll /keyfile:MyKey.snk
I then copied the file to the appropriate location and built the project, but each time the build failed on the following error: Assembly generation failed -- Referenced assembly 'Interop.WindowsInstaller' does not have a strong name.
I thought the problem was with the tlbimp line, but after reading Karel Zikmund's reply and verifying that the DLL is strong-named (using sn -vf Interop.WindowsInstaller) I found out the problem.
Adding a reference to the "Microsoft Windows Installer Object Library" COM object actually planted a code block into the .csproj file.
I didn't realize it, but this block caused the DLL file to be regenerated from scratch upon each time the project was built. The generated file, of course, was not strong-named anymore.
The way I resolved it was to remove the reference to "Microsoft Windows Installer Object Library" from the project, and add a direct file reference to the imported (and already signed) Interop.WindowsInstaller.dll file.