O firewall estava faltando uma regra para pacotes UDP de entrada na porta 500. Isso deveria ter sido gerado automaticamente, mas (às vezes) falhou.
Depois de adicionar essa regra manualmente, o problema foi resolvido. O projeto IPfire também criou um patch que provavelmente corrigirá a causa raiz.