A solução foi excluir (preferencialmente renomear) o arquivo cert8.db na pasta de perfis do Thunderbird.
Não sei por que isso funciona e o que exatamente faz com que, de repente, de um dia para o outro, TB não seja autenticado corretamente no servidor, mas essa solução funciona. Lembrei-me desta solução de um tempo anterior, quando me deparei com um problema semelhante. Deve haver alguns fóruns nos quais esta solução é sugerida.
Sugiro não excluir, mas apenas renomeie o arquivo cert8.db. Se no seu caso isso não resolver o problema, você poderia facilmente colocar o arquivo cert8.db original de volta.
O local exato para encontrar o arquivo (no Linux): /home/user/.thunderbird/yourPrOf1le.default/.