May it be that verification compares only against addresses created by Mycelium? Because the address I am trying to verify is imported external address.
Yes, i can confirm that.
Just imported a random private key into mycelium and made a backup.
Upon trying to verify it, i received the same error message ("
The key does not correspond to any bitcoin address").
Seems like it is a bug.
The best in your situation would be to backup the private key itself, or encrypt it yourself (using BIP38).