Então, eu mesmo encontrei a solução, embora não fosse um problema de correio.
Eu tenho um erro na minha tabela de pesquisa do dns que teve o efeito de que o kmail tentou se conectar a um host na Internet que não é o servidor correto.
Depois de remover o erro no DNS, tudo correu bem. Ish acontece!