Tirei um tempo para ler alguns e-mails antigos e, para minha surpresa havia uma dica da Dicas-L que falava exatamente sobre impressão de e-mails com o mutt + muttprint. Testei a solução apresentada e o resultado foi espetacular.

A dica eu transcrevo abaixo:

 Imprimindo e-mail com mutt e muttprint
  ======================================
Colaboração: Francisco A Silva
Data de Publicação: 01 de January de 2009                                                                                 

Normalmente quando usamos o mutt para ler e-mail's e precisamos imprimir o
documento, temos um resultado impresso pouco satisfatório. Para resolver
este problema, temos o muttprint (aptitude install muttprint),
que permite uma impressão excelente e totalmente customizável.                                                            

Insira so seu .muttrc (/home/usuario/.muttrc) as seguintes linhas:                                                        

  set print_cmd="muttprint -p duplex-letter"                                                                              

altere também o arquivo .muttprintrc do seu home para o seguinte:                                                                                                                                                                                   

  # MUTTPRINT configuration file
  #
  # ~/.muttprintrc or /etc/Muttprintrc
  # ~/.muttprintrc
  XFACE="off"
  DUPLEX="printer"
  PAPERSAVE="off"
  SPEED="80"
  FONT="Latex"
  FRONTSTYLE="fbox"
  HEADRULE="on"
  FOOTRULE="on"
  PAPER="A4"
  REM_SIG="on"
  SIG_REGEXP="^-- $"
  REM_QUOTE="off"
  PRINTED_HEADERS="Date_To_From_CC_Newsgroups_*Subject*"
  DEBUG="1"
  FONTSIZE="10pt"
  WRAPMARGIN="90"
  TOPMARGIN="19"
  BOTTOMMARGIN="22"
  LEFTMARGIN="20"
  RIGHTMARGIN="20"
  DATE="original"
  VERBATIMNORMAL=""
  VERBATIMSIG="fontshape=it"
  ADDRESSFORMAT="%r <%a>,\n"                                                                                              

O arquivo tem muitas outras possibilidades de impressão de acordo com cada
necessidade como por exemplo, duas paginas na mesma face de impressão.

E a dica pode ser encontrada em: http://www.dicas-l.com.br/print/20090101.html

O único porém (para alguns) é que o muttprint usa o LaTeX para formatar o texto. Para mim, que já tinha ele instalado, não houve problema algum