We use fully-trusted Infopath forms a lot here at work. Yesterday I had one that was “stuck”. It didn't show up in add/remove programs, but when I tried to re-install it I was told it was already installed. Also, you couldn't manually remove it with msiexec, it would say that the form isn't installed. Kinda aggrivating...
So I did a little searching in the registry and found where the form was at:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Office\11.0\InfoPath\SolutionsCatalog
Just rename or delete the key that is your fully-trusted form and you should be able to reinstall it again.