Depois de ler o código-fonte do fetchmail (sink.c, em torno da linha 1183), não consegui descobrir uma maneira de codificar '%'.
Portanto, a única alternativa é evitar "% s", e é fácil usar a sintaxe de cotação única do bash:
mda "/bin/sh -c 'cat > INBOX/new/$(date +%''s_%N)'"