The man himself Tanguy “The XRM Toolbox” Touzard has the podium today:

If you are getting the error code -2147089917 while trying to uninstall managed solution and the message reads “[entity] did not have a valid Quickfind query”, verify that the entity is not in the list of entities enabled for multi-entity quick search:

Settings > Administration > System Settings then General tab > Set up Quick Find (heading) > Select entities for search > Select…