Existem dois avisos diferentes aqui, e acho que os outros respondedores estão assumindo que um é causado pelo outro.
Suponho que a advertência "a mensagem não foi protegida por integridade" é sua principal preocupação, já que esse é o título dessa pergunta. Parece haver várias coisas que podem causar isso, mas a que acabei de encontrar é quando o recurso "Proteção MDC" do GPG não está habilitado. Eu não sei o que isso significa, mas aparentemente é uma verificação de integridade da mensagem que prova que a mensagem não foi adulterada.
Aparentemente, esse recurso está ativado por padrão, mas fica desabilitado se alguma das chaves do destinatário não especificar que ele é compatível. Então, acabei de receber o aviso pela primeira vez ao adicionar um novo destinatário a um arquivo que eu estava criptografando apenas para mim, presumivelmente porque o novo destinatário não disse que suportava o MDC.
Recebi o aviso para ir adicionando --force-mdc
ao meu comando GPG. Ainda não descobri se isso impede que o novo destinatário descriptografe a mensagem ...
Tenho certeza de que o outro aviso, sobre a chave não ser confiável, não está relacionado ao aviso "não protegido por integridade".