Sua primeira pergunta ("Por que eu preciso de uma chave secreta para assinar uma chave pública?") é direta: é assim que funciona a criptografia de chave pública. Assinar algo (uma chave, um documento etc.) usa sua chave privada e pode ser verificado usando sua chave pública. A criptografia usa sua chave pública e pode ser descriptografada usando sua chave privada.
Sua segunda pergunta está mais envolvida. Você assinar ou não assinar a chave não deve importar - a assinatura só impedirá que avisos sobre a chave não sejam confiáveis; é uma parte importante da web-of-trust que o PGP / GPG é construído. Mas, se você verificou a exatidão da chave fora da rede de confiança (por exemplo, recebendo-a diretamente do destinatário), poderá ignorar a rede de confiança. Portanto, nenhuma assinatura deve ser necessária.
O que eu acho que está acontecendo é que você está usando um argumento -r diferente da impressão digital de chave completa - e você está acidentalmente criptografando para o destinatário errado. Você deve usar a impressão digital completa (por exemplo, 067E3C456BAE240ACEE88F6FEF0F382A1A7B6500 , não a curta EF0F382A1A7B6500 e certamente não a muito curta 1A7B6500 ).
A única outra coisa em que consigo pensar é que você está usando (provavelmente sem saber) algum algoritmo que o lado da descriptografia não suporta. Por exemplo, se você estiver usando uma versão muito mais recente do gnupg do que o destinatário. Ou o destinatário está usando algum outro programa. É normal que a chave do destinatário especifique o que o programa suporta, mas possivelmente a chave específica não está certa ou está errada. O GPG tem opções para substituir (consulte a página do manual em "INTEROPERABILITY", mas vale a pena tentar --pgp8 , --pgp7 e --pgp6 ).