You could use Msiexec to remove the software.
MSIEXEC /uninstall Product.msi
MSIEXEC /x Product.msi
MSIEXEC /uninstall ProductCode
MSIEXEC /x ProductCode
If you know the installer that was used to install with, you could create a software distribution package and use the uninstall switches to remove it.
As a further preventive measure, I'd suggest probably adding to the list of blocked applications, if that's the battle you're fighting?
That way, the app process gets killed off when it attempts to launch - and doesn't rely on you / a policy uninstalling it.