If excludes are specified on command line or config file, they hide even installed RPMs (base.sack.query().installed()) This affects how rpmdb version for the history database is computed. An option how to implement it is to move computing rpmdb version into libdnf and use query with HY_IGNORE_EXCLUDES flag.
I create a patch that should solve the issue (https://github.com/rpm-software-management/dnf/pull/1234).
dnf-plugins-core-4.0.0-1.fc29 dnf-4.0.4-1.fc29 libdnf-0.22.0-1.fc29 has been submitted as an update to Fedora 29. https://bodhi.fedoraproject.org/updates/FEDORA-2018-2789f6b6e7
dnf-4.0.4-1.fc29, dnf-plugins-core-4.0.0-1.fc29, libdnf-0.22.0-1.fc29 has been pushed to the Fedora 29 testing repository. If problems still persist, please make note of it in this bug report. See https://fedoraproject.org/wiki/QA:Updates_Testing for instructions on how to install test updates. You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2018-2789f6b6e7
dnf-4.0.4-1.fc29 dnf-plugins-core-4.0.0-2.fc29 libdnf-0.22.0-2.fc29 has been submitted as an update to Fedora 29. https://bodhi.fedoraproject.org/updates/FEDORA-2018-2789f6b6e7
dnf-4.0.4-1.fc29, dnf-plugins-core-4.0.0-2.fc29, libdnf-0.22.0-2.fc29 has been pushed to the Fedora 29 testing repository. If problems still persist, please make note of it in this bug report. See https://fedoraproject.org/wiki/QA:Updates_Testing for instructions on how to install test updates. You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2018-2789f6b6e7
anaconda-29.24.6-1.fc29 dnf-4.0.4-1.fc29 dnf-plugins-core-4.0.0-2.fc29 libblockdev-2.20-2.fc29 libdnf-0.22.0-2.fc29 has been submitted as an update to Fedora 29. https://bodhi.fedoraproject.org/updates/FEDORA-2018-2789f6b6e7
anaconda-29.24.7-1.fc29, dnf-4.0.4-1.fc29, dnf-plugins-core-4.0.0-2.fc29, libblockdev-2.20-2.fc29, libdnf-0.22.0-5.fc29 has been pushed to the Fedora 29 testing repository. If problems still persist, please make note of it in this bug report. See https://fedoraproject.org/wiki/QA:Updates_Testing for instructions on how to install test updates. You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2018-2789f6b6e7
anaconda-29.24.7-1.fc29, dnf-4.0.4-1.fc29, dnf-plugins-core-4.0.0-2.fc29, libblockdev-2.20-2.fc29, libdnf-0.22.0-5.fc29 has been pushed to the Fedora 29 stable repository. If problems still persist, please make note of it in this bug report.