The "Update configuration check status" compares the assigned application configuration for a specified user to the contents of the SyncDeviceManagement table in the database. So it does not actually look on the device itself.
You also have to check the other statuses, they should look like:
Configuration Status: OK
System Status: Up to date
Application Status: Up to date
Also, how did you make sure that the application is not installed? Have you looked in the Options > Application
You should also check the User Properties > Blackberry device > Applications on the BES. Is the app listed there?