After serveral clever attempt, I've settled to this simple workaround that seems working despite being quite inefficient: if you don't find any key with gpgme_op_keylist_next and gpgme_err_code(err) == GPG_ERR_EOF on a ctx with keylist mode set to GPGME_KEYLIST_MODE_LOCATE, try again (even on the same context), after

Looking to workaround this issue, I've noticed something that might be useful during debug.