Assigning software through group policy – how does client know if the package is installed or not

I'm recently trying to use group policy to push out some software at our company. We're running server 2008 R2. When I create the computer GPO and assign the package it will install the first time. However, since this is a new process for me and I want to test it, I uninstalled the software to try different scenarios such as having the previous version of the software installed.

So, I manually uninstall the software and when I reboot it doesn't even try to reinstall. I've tried various settings such as going to tasks > redeploy application and then rebooting and setting the "Software Installation Policy processing" to "Process even if the Group Policy objects have not changed." As I understand it both of these methods should force a reinstall regardless if it's been installed or not. Also, there is nothing in the logs (errors or otherwise) about software installing.

I have verbose status message turned on and it says something about installing software from policy at startup but that is it. I saw in a few threads that you can delete the registry entry that the client uses to determine if the software is installed etc…

My question is, is this the default behavior for software deployment via group policy? Is it not working correctly because I manually removed it via programs and features and maybe windows still thinks it's installed? If that was the case, wouldn't the redeploy application still force a new install even if it was already installed? Any help would be appreciated. Thanks!