¿En la página HTML que compones para mostrar esos mensajes/títulos usas definición de CharSet tipo?:
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
También tienes otras funciones sobre "Charset" .. (no sé si serán las que necesitas ..pero es bueno tenerlas presente).
http://www.php.net/imap_mime_header_decode
Un saludo,