I've found a couple of separate issues potentially, which seem to be
connected. Not sure how to log this, so here is one bug explaining it.
Basically I had created some test keys and then deleted them before
"productionising" the GPG solution I use. I had to import a private key from
a server where it was used before and the key has no User ID. Well, it does
show a single word (company name), but the following happens. After
importing it, I try to edit it by providing this single word user id. And it
goes into edit mode for one of those old keys instead. That old (deleted!)
secret key is not listed by "gpg -K". Yet it shows somehow? And the weird
thing is that this has a proper long User ID (which is not the same as this
new key I have just imported).
So I try to edit using the key id. But it says "gpg: key 'keyid...' not
found: No public key". However - if I try deleting it usign the same key id

• it works!

sec xxxxx/keyid... 2013-01-03 [User ID not found]
Delete this key from the keyring? (y/N)

Again, I might have described a couple of different issues here, but not
knowing what's causing what, it's hard for me to separate these.