Then I tried it at Kleopatra. I tried to import the public key via the Tools menu -> Clipboard -> Certificate Import (I see this method is not in the OP).
I don't have that option (in Kleopatra, running Linux) under the Tools menu, but it works from the system tray. I have the Certificate imported under "Other Certificates".
Then verify the message
I did this also from the system tray, but get this:

I have no idea how to procees

I have another message I want to verify (
for a potential scam accusation thread), and that one I can't share.