A resposta foi encontrada. Graças a Phil :)
Exim is being very carefully adherent to the MIME specification in RFC2047 which places a maximum length on each encoded-word.
----------------------------8< cut here >8------------------------------
encoded-word = "=?" charset "?" encoding "?" encoded-text "?=" [...]
An 'encoded-word' may not be more than 75 characters long, including 'charset', 'encoding', 'encoded-text', and delimiters. If it is desirable to encode more text than will fit in an 'encoded-word' of 75 characters, multiple 'encoded-word's (separated by CRLF SPACE) may be used.
----------------------------8< cut here >8------------------------------
So the MIME decoder is skipping those long strings and adding them literally.
...
If you set "check_rfc2047_length" false in Exim's main configuration, the header will be decoded correctly; I would assume (but haven't checked) that Exim would then re-encode things correctly as needed.
check_rfc2047_length = false
Portanto, após definir check_rfc2047_length = false
, todas as variações de assuntos problemáticos serão decodificadas corretamente.