Yup - HTML composition was the key.  Fixed.  Thanks for helping to 
track this down.

Changes have been made in Git for this ticket:

Bug #8837: Fix headers charset when doing HTML compose

http://git.horde.org/diff.php/imp/lib/Compose.php?rt=horde-git&r1=12e455a324a5a44ca84c3d8939d50484eb9d9ad8&r2=143c683eb12bb899880da182a74667297e7359be

output when composing as plain text :

Horde_Mime_Part Object
(
     [_type:protected] => text
     [_subtype:protected] => plain
     [_contents:protected] => Resource id #28
     [_transferEncoding:protected] => binary
     [_description:protected] =>
     [_disposition:protected] => inline
     [_dispParams:protected] => Array
         (
         )

     [_contentTypeParams:protected] => Array
         (
             [charset] => ISO-8859-1
             [format] => flowed
             [DelSp] => Yes
         )

     [_parts:protected] => Array
         (
         )

     [_mimeid:protected] =>
     [_eol:protected] =>

     [_temp:protected] => Array
         (
             [toString] =>
             [sendTransferEncoding] => Array
                 (
                     [1] => 7bit
                 )

             [transferEncodeClose] =>
         )

     [_metadata:protected] => Array
         (
         )

     [_boundary:protected] =>
     [_bytes:protected] =>
     [_contentid:protected] =>
     [_reindex:protected] =>
     [_basepart:protected] => 1
     [_hdrCharset:protected] =>
)

Composing as plain text like you, I don't have this issue! Here is 
$message when composing as HTML:

Horde_Mime_Part Object
(
     [_type:protected] => multipart
     [_subtype:protected] => alternative
     [_contents:protected] =>
     [_transferEncoding:protected] => binary
     [_description:protected] =>
     [_disposition:protected] => inline
     [_dispParams:protected] => Array
         (
         )

     [_contentTypeParams:protected] => Array
         (
             [boundary] => =_ey9kh8syst4cs8g0044wk88s
         )

     [_parts:protected] => Array
         (
             [0] => Horde_Mime_Part Object
                 (
                     [_type:protected] => text
                     [_subtype:protected] => plain
                     [_contents:protected] => Resource id #35
                     [_transferEncoding:protected] => binary
                     [_description:protected] => Plaintext Version
                     [_disposition:protected] => inline
                     [_dispParams:protected] => Array
                         (
                         )

                     [_contentTypeParams:protected] => Array
                         (
                             [charset] => ISO-8859-1
                             [format] => flowed
                             [DelSp] => Yes
                         )

                     [_parts:protected] => Array
                         (
                         )

                     [_mimeid:protected] =>
                     [_eol:protected] =>

                     [_temp:protected] => Array
                         (
                             [toString] =>
                             [sendTransferEncoding] => Array
                                 (
                                     [1] => 7bit
                                 )

                             [transferEncodeClose] =>
                         )

                     [_metadata:protected] => Array
                         (
                         )

                     [_boundary:protected] =>
                     [_bytes:protected] =>
                     [_contentid:protected] =>
                     [_reindex:protected] =>
                     [_basepart:protected] =>
                     [_hdrCharset:protected] =>
                 )

             [1] => Horde_Mime_Part Object
                 (
                     [_type:protected] => text
                     [_subtype:protected] => html
                     [_contents:protected] => Resource id #38
                     [_transferEncoding:protected] => binary
                     [_description:protected] => HTML Version
                     [_disposition:protected] => inline
                     [_dispParams:protected] => Array
                         (
                         )

                     [_contentTypeParams:protected] => Array
                         (
                             [charset] => ISO-8859-1
                         )

                     [_parts:protected] => Array
                         (
                         )

                     [_mimeid:protected] =>
                     [_eol:protected] =>

                     [_temp:protected] => Array
                         (
                             [toString] =>
                             [sendTransferEncoding] => Array
                                 (
                                     [1] => 7bit
                                 )

                             [transferEncodeClose] =>
                         )

                     [_metadata:protected] => Array
                         (
                         )

                     [_boundary:protected] =>
                     [_bytes:protected] =>
                     [_contentid:protected] =>
                     [_reindex:protected] =>
                     [_basepart:protected] =>
                     [_hdrCharset:protected] =>
                 )

         )

     [_mimeid:protected] =>
     [_eol:protected] =>

     [_temp:protected] => Array
         (
             [toString] =>
             [sendTransferEncoding] => Array
                 (
                     [1] => 7bit
                 )

         )

     [_metadata:protected] => Array
         (
         )

     [_boundary:protected] => =_ey9kh8syst4cs8g0044wk88s
     [_bytes:protected] =>
     [_contentid:protected] =>
     [_reindex:protected] => 1
     [_basepart:protected] => 1
     [_hdrCharset:protected] =>
)

charset isn't set in the top object, that's probably why IMP gets 
confuse between UTF-8 (probably default value if not set) and 
ISO-8859-1 (set when composing)

Incorrect.  If a specific header encoding is not defined for a message 
part, we use the charset defined for the body.  We don't define a 
charset for the headers in IMP, so the charset of the body is the 
important factor here.

On line 762 of imp/lib/Compose.php, can you put a print_r($message) 
and post the output.  A test for me gives:

Horde_Mime_Part Object
(
     [_type:protected] => text
     [_subtype:protected] => plain
     [_contents:protected] => Resource id #22
     [_transferEncoding:protected] => binary
     [_description:protected] =>
     [_disposition:protected] => inline
     [_dispParams:protected] => Array
         (
         )

     [_contentTypeParams:protected] => Array
         (
             [charset] => UTF-8
             [format] => flowed
             [DelSp] => Yes
         )

     [_parts:protected] => Array
         (
         )

     [_mimeid:protected] =>
     [_eol:protected] =>

     [_temp:protected] => Array
         (
         )

     [_metadata:protected] => Array
         (
         )

     [_boundary:protected] =>
     [_bytes:protected] =>
     [_contentid:protected] =>
     [_reindex:protected] =>
     [_basepart:protected] => 1
     [_hdrCharset:protected] =>
)

As expected, _hdrCharset is empty and charset is set to the sending 
charset value (in this case, UTF-8).

The body is fine. The issue is with the header.

using default prefs and config options;
when buildAndSendMessage is called, $charset is set to 'ISO-8859-1'

I've attached the full email sent. In the header, field 'To', if I 
replace 'utf-8' with 'iso-8859-1', email is display fine. So the 
header is encoded just fine, like the body. I just can't find out 
where the 'utf-8' is coming from!

This still doesn't make any sense. Any message sent via IMP *must* 
have the charset set on the body - this is done in 
IMP_Compose::_createMimeMessage().  That's the only reason $charset 
would be empty inside of Horde_Mime_Part when the message is created.

Could you possibly add some debugging statements at the top of 
IMP_Compose::_createMimeMessage() to see if $charset is empty there?

framework/Horde/Mime/Part.php:1493
$result = $mailer->send(Horde_Mime::encodeAddress($email, 
$this->getCharset()), $headers->toArray(array('charset' => 
$this->getHeaderCharset())), $msg);

$this->getHeaderCharset() doesn't return anything.
If I replace $this->getHeaderCharset() with 'iso-8859-1',and send 
message using charset 'iso-8859-1' => OK
If I replace $this->getHeaderCharset() with 'utf-8', and send message 
using charset 'utf-8' => OK
any other cases fail to send/display email correctly.

I don't known where to go from there.

I've set pref $_prefs['sending_charset'] = array( 'value' => 
'utf-8',..) and everything is working fine. So, I guess I'm happy with 
this.

If you need me to do more testing/tracking, you'll have to tell me how to.

further testing :
- click on new message, charset is set to "Western (ISO-8859-1)", and 
send a message to : Céline <email>
=> header looks like : To: =?utf-8?b?Q+lsaW5l?= <email>
- click on new message, change charset to "Unicode (UTF-8)", and send 
a message to : Céline <email>
=> Email displayed as expected and header looks like : To: 
=?utf-8?b?Q8OpbGluZQ==?= <email>

Forgot to mention that when composing a new email, the Charset option 
is set to "Western (ISO-8859-1)" by default.

here some prefs. the following are set to the default values.

$_prefs['sending_charset'] = array(
     'value' => '',
     'locked' => false,
     'shared' => true,
     'type' => 'enum',
     'enum' => array_merge(array('' => _("Default")), 
Horde_Nls::$config['encodings']),
     'desc' => _("Your default charset for sending messages:"));

$_prefs['default_msg_charset'] = array(
     'value' => isset($GLOBALS['nls']['emails'][$GLOBALS['language']])
         ? $GLOBALS['nls']['emails'][$GLOBALS['language']]
         : (isset($GLOBALS['nls']['charsets'][$GLOBALS['language']])
             ? $GLOBALS['nls']['charsets'][$GLOBALS['language']]
             : ''),
     'locked' => false,
     'shared' => false,
     'type' => 'enum',
     'enum' => array_merge(
         array('' => _("Default (US-ASCII)")), Horde_Nls::$config['encodings']
     ),
     'desc' => _("The default charset for messages with no charset 
information:"),
     'help' => 'prefs-default_msg_charset');

Reading your comment, the encoded string look like the same :
yours : To: =?iso-8859-1?b?Q+lsaW5l?= <test@example.com>
mine :            To: =?utf-8?b?Q+lsaW5l?= <mysefl@work.com>


If I edit the source of the message and change "utf-8" to 
"iso-8859-1", header is displayed fine in IMP.

I don't see this.  Sending a message gives me the following (trying 
both ISO-8859-1 and UTF-8):

To: =?iso-8859-1?b?Q+lsaW5l?= <test@example.com>

To: =?utf-8?b?Q8OpbGluZQ==?= <test@example.com>

You might try to poke around Horde_Mime::encodeAddress() to figure out 
why it isn't working correctly.

I did send it twice to myself : Once using IMP and once using DIMP. In 
both case, the emails sent/received look like the same (INBOX or 
INBOX.Sent).
Using thunderbird 2.0.0.18 :
- emails sent to (from IMP) : Céline <mysefl@work.com>
=> Receiver appears as a question mark icon

- if I send an email to (using thunderbird) : Céline <mysefl@work.com>
=> header is : To: =?ISO-8859-1?Q?C=E9line?= <rsalmon@mbpgroup.com>
=> Appears just fine in IMP (INBOX and INBOX.Sent)

Do you send this message to yourself, or is this message in your 
sent-mail folder? Does this happen when sending or reading messages, 
i.e. what happens if you use a different client for either of those?

I use Firefox 3.5.7/linux
I compose and send a new message to : Céline <mysefl@work.com>, then 
access my mailbox

Here is the source of the message's header :
From: mysefl@work.com
To: =?utf-8?b?Q+lsaW5l?= <mysefl@work.com>


Output from IMP :
To:          C&#65533;line <mysefl@work.com>        <subject>....

Output from DIMP :
[Invalid Address]          <subject>....