Is it possible, that you have installed more kernel packages that is allowed by `installonly_limit` in /etd/dnf/dnf.conf (default value is 3)?
On my system I set the limit to two, having three kernels installed:

❯ dnf5 --dump-main-config | grep installonly_limit
installonly_limit = 2

❯ rpm -q kernel-core
kernel-core-6.12.15-100.fc40.x86_64
kernel-core-6.13.4-100.fc40.x86_64
kernel-core-6.13.5-100.fc40.x86_64

Than I can observe the same strange behavior:

❯ dnf5 install acpi
Package                     Arch     Version                     Repository          Size
Removing:
 kernel                     x86_64   6.12.15-100.fc40            updates          0.0   B
 kernel-core                x86_64   6.12.15-100.fc40            updates         73.6 MiB
 kernel-modules             x86_64   6.12.15-100.fc40            updates         62.4 MiB
 kernel-modules-core        x86_64   6.12.15-100.fc40            updates         37.1 MiB
 kernel-modules-extra       x86_64   6.12.15-100.fc40            updates          2.7 MiB
Installing:
 acpi                       x86_64   1.7-23.fc40                 fedora          47.5 KiB

Transaction Summary:
 Installing:         1 package
 Removing:           5 packages

Total size of inbound packages is 27 KiB. Need to download 27 KiB.
After this operation, 176 MiB will be freed (install 47 KiB, remove 176 MiB).
Is this ok [y/N]: 
Operation aborted by the user.

Which is definitelly not expected.

Regarding the "Package was not found in rpm database" error. It unfortunately does not say which package was not found in the rpm database. But according dnf5 sources, this error can only occur during package removal, so it has to be one of the kernel* packages that were going to be removed.
I was able to reproduce the error using two terminal sessions:

Terminal#1:

❯ dnf remove acpi
Package                     Arch     Version                     Repository          Size
Removing:
 acpi                       x86_64   1.7-23.fc40                 fedora          47.5 KiB

Transaction Summary:
 Removing:           1 package

After this operation, 47 KiB will be freed (install 0 B, remove 47 KiB).
Is this ok [y/N]:

Now, before confirming the transaction, I removed the acpi package using rpm in Terminal#2:

❯ rpm -e acpi

Back to Terminal#1:
Is this ok [y/N]: y
Running transaction
Package was not found in rpm database


Is it possible that something similar could have happened on your system? Like another package manager removed the kernel package after the `dnf update -y dnf*` command was issued, but before the transaction confirmed?

(In reply to Marek Blaha from comment #1)
> Is it possible, that you have installed more kernel packages that is allowed
> by `installonly_limit` in /etd/dnf/dnf.conf (default value is 3)?
> On my system I set the limit to two, having three kernels installed:

No. There have always been 3 Kernels on that system, as i should be. More wouldn't fit into /boot, which is classical 500MB in size ;)

(In reply to Marek Blaha from comment #2)
> Regarding the "Package was not found in rpm database" error. It
> unfortunately does not say which package was not found in the rpm database.

So it got deleted earlier, before dnf could remove it.

> Is it possible that something similar could have happened on your system?
> Like another package manager removed the kernel package after the `dnf
> update -y dnf*` command was issued, but before the transaction confirmed?

There should not be another manager active, but there is a cron job running every 2h to auto update packages.

But as dnf is setting a transaction lock, it should not be possible to proceed until that is gone.
usually there is a message telling the user, that his process is waiting for another process to finish.
That message was not present.

I'm absolutly open to the accidently co-running dnf cron, what do you think?

(In reply to customercare from comment #3)
> (In reply to Marek Blaha from comment #1)
> > Is it possible, that you have installed more kernel packages that is allowed
> > by `installonly_limit` in /etd/dnf/dnf.conf (default value is 3)?
> > On my system I set the limit to two, having three kernels installed:
> 
> No. There have always been 3 Kernels on that system, as i should be. More
> wouldn't fit into /boot, which is classical 500MB in size ;)

I filed a separate upstream issue for kernels removal during completely unrelated transaction: https://github.com/rpm-software-management/dnf5/issues/2127

The conflict between cron job running dnf update and dnf from console is quite possible.
Here is the upstream issue tracking these conflicts: https://github.com/rpm-software-management/dnf5/issues/492 . It was filed for upgrade/remove conflict, but will behave the same for upgrade/upgrade.

This message is a reminder that Fedora Linux 41 is nearing its end of life.
Fedora will stop maintaining and issuing updates for Fedora Linux 41 on 2025-12-15.
It is Fedora's policy to close all bug reports from releases that are no longer
maintained. At that time this bug will be closed as EOL if it remains open with a
'version' of '41'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, change the 'version' 
to a later Fedora Linux version. Note that the version field may be hidden.
Click the "Show advanced fields" button if you do not see it.

Thank you for reporting this issue and we are sorry that we were not 
able to fix it before Fedora Linux 41 is end of life. If you would still like 
to see this bug fixed and are able to reproduce it against a later version 
of Fedora Linux, you are encouraged to change the 'version' to a later version
prior to this bug being closed.

Upstream still open