Created attachment 1762003 [details]
Error message shown.
Description of problem:
I used Gnome-Software to install EasyTag (easytag). The package was successfully installed which I checked using `rpm -qa easytag`.
Then, immediately after that, I changed my mind and uninstalled the package again.
The package was removed from the system but Gnome Software still shows that it is installed and reports that it cannot be uninstalled at the same time.
Version-Release number of selected component (if applicable):
Steps to Reproduce:
1. Open Software.
2. Install application.
3. Click on "Start"
4. Wait until app starts.
5. Click on Uninstall.
6. After a while, the red Uninstall button appears.
7. Click on that button.
Application reports an error: No package to remove.
rpm -qa says it is uninstalled.
Application should update according the real status quo.
Restarting the application does not help. After rebooting, the application is correctly recognized as uninstalled, but when I repeat the reproducer, I arrive at the same result.
This behaviour only happens for the first time installation after a reboot. Other installations seem to behave correctly.
The first installed application is marked installed until the machine is rebooted.
Nothing is seen in journal.
See screenshots attached.
Proposed as a Blocker for 34-final by Fedora user lruzicka using the blocker tracking app because:
This behaviour is not very serious, so I am just proposing it for discussion, because it happens in the important Gnome application installed by default.
Discussed during the 2021-03-15 blocker review meeting: 
The decision to classify this bug as a "RejectedBlocker (Final)" was made as this doesn't seem to constitute a criterion violation, the essential functions work, and the sync issue is transient (solved with a reboot).
This is fixed with changes from https://gitlab.gnome.org/GNOME/gnome-software/-/issues/630 aka https://gitlab.gnome.org/GNOME/gnome-software/-/merge_requests/642 .
The upstream changes had been committed for 40.1, thus I'm closing this.