Hello and welcome to Advanced Installer forums,
Upon installing a setup, a cache of the MSI is stored in the Windows\Installer folder.
Upon uninstalling, if the setup is not present on the machine, the earlier mentioned cache is used to perform the uninstall.
In what regards the UAC, that may happen (the publisher is shown as unknown) if your package is not digitally signed. If the package is digitally signed, the publisher should be shown as known (e.g. it would show the manufacturer) and that would give your users no reasons to be concerned.
For more information about this, please have a look on the following articles:
Digital Signature
Digital Signature Page
Hope this helps.
Best regards,
Catalin