I'm 100% sure that a few days ago we still didn't have this bug, so I
guess it is related to the DB 4.6 upgrade. Just now with the latest HEAD
(without any local patches):

| $ ls -l /tmp/rpm/var/rpm/db
| total 0
| $ /tmp/rpm/bin/rpm --initdb
| $ ls -l /tmp/rpm/var/rpm/db
| total 88
| -rw-r--r--  1 rse  wheel     8192 Jul 29 17:13 Packages
| -rw-r--r--  1 rse  wheel    24576 Jul 29 17:13 __db.001
| -rw-r--r--  1 rse  wheel    57344 Jul 29 17:13 __db.002
| -rw-r--r--  1 rse  wheel  1318912 Jul 29 17:13 __db.003
| -rw-r--r--  1 rse  wheel   475136 Jul 29 17:13 __db.004
| $ /tmp/rpm/bin/rpm --import pubkeys/JBJ-GPG-KEY
| $ ls -l /tmp/rpm/var/rpm/db
| total 156
| -rw-r--r--  1 rse  wheel     8192 Jul 29 17:13 Group
| -rw-r--r--  1 rse  wheel     8192 Jul 29 17:13 Installtid
| -rw-r--r--  1 rse  wheel     8192 Jul 29 17:13 Name
| -rw-r--r--  1 rse  wheel    12288 Jul 29 17:13 Packagecolor
| -rw-r--r--  1 rse  wheel    12288 Jul 29 17:13 Packages
| -rw-r--r--  1 rse  wheel     8192 Jul 29 17:13 Providename
| -rw-r--r--  1 rse  wheel     8192 Jul 29 17:13 Provideversion
| -rw-r--r--  1 rse  wheel    12288 Jul 29 17:13 Pubkeys
| -rw-r--r--  1 rse  wheel    24576 Jul 29 17:13 __db.001
| -rw-r--r--  1 rse  wheel    57344 Jul 29 17:13 __db.002
| -rw-r--r--  1 rse  wheel  1318912 Jul 29 17:13 __db.003
| -rw-r--r--  1 rse  wheel   475136 Jul 29 17:13 __db.004
| $ /tmp/rpm/bin/rpm -qa
| gpg-pubkey-2039b291-3dbaae72.(none)
| $ /tmp/rpm/bin/rpm -e "gpg-pubkey-2039b291-3dbaae72"
| error: ^2039b291$: regcomp failed:
| error: package gpg-pubkey-2039b291-3dbaae72 is not installed
| $ /tmp/rpm/bin/rpm -qa
| Freeing locks for locker 0xe: 22298/0
| Freeing locks for locker 0xf: 22298/0
| Freeing locks for locker 0x10: 22298/0
| gpg-pubkey-2039b291-3dbaae72.(none)
| $ /tmp/rpm/bin/rpm -qa
| gpg-pubkey-2039b291-3dbaae72.(none)

Please notice that until the erase operation everything was just fine.
Then the key is not found (although correctly specified), the database
is then locked and even after removing the locks the key is still not
gone...
                                       Ralf S. Engelschall
                                       rse@engelschall.com
                                       www.engelschall.com