I have checked that I have Horde_Mime 1.3.0 installed where 10696 is 
addressed, but my sendmail problem persists. I have just tried revert 
to Horde_Mime 1.2.1 and the error goes away. So the problem is still 
there in 1.3.0.

Yes.  Confirmed that this was a duplicate of Ticket #10696.

Are those patches already rolled out to the pear channel? I have the 
latest packages and the problems are still there. I tried downgrading 
the Horde_Imap_Client without success...

Sounds like a duplicate of Ticket #10696.

When sending a message the log entries in Exim have changed as well

Before:
2011-07-07 22:03:12 1Qeun0-00035x-GQ <= xxx@xxx.de U=www-data P=local 
S=3700 id=20110707220310.Horde.OAYRCemkpHVOFhD_Z3DTyeA@wwxxxn.de
2011-07-07 22:03:13 1Qeun0-00035x-GQ => xxx@yahoo.de R=smarthost_tau 
T=remote_smtp_smarthost H=smtp.1und1.com [212.227.15.145] 
X=TLS1.0:RSA_AES_256_CBC_SH$
2011-07-07 22:03:13 1Qeun0-00035x-GQ Completed

After:
2011-11-11 00:54:09 1ROeRc-0001Kh-4F <= xxx@xxx.de U=www-data P=local S=1457
2011-11-11 00:54:09 1ROeRc-0001Kh-4F => xxx@gmx.de R=smarthost_tau 
T=remote_smtp_smarthost H=smtp.1und1.com [212.227.15.129] 
X=TLS1.0:RSA_AES_256_CBC_SHA1:32 
DN="C=DE,ST=Rheinland-Pfalz,L=Montabaur,O=1 und 1 Internet 
AG,CN=smtp.1und1.com"
2011-11-11 00:54:09 1ROeRc-0001Kh-4F Completed

I have tested sending a message to a local user directly (no external 
mail server involved). This time Exim inserted some extra headers 
right in the middle of the message...

Return-path: <xxg@rxxxen.de>
Envelope-to: jule@localhost
Delivery-date: Fri, 11 Nov 2011 00:25:35 +0100
Received: from www-data by xxxerver.info with local (Exim 4.75)
        (envelope-from <hxxg@rxxxxn.de>)
        id 1ROdzx-0000u7-Po
        for jule@localhost; Fri, 11 Nov 2011 00:25:35 +0100
Received: from xxx65.unitymediagroup.de
  (ixxx.unitymediagroup.de [178.200.154.165]) by xxgen.de
  (Horde Framework) with HTTP; Fri, 11 Nov 2011 00:25:33 +0100
  Date: Fri, 11 Nov 2011 00:25:33 +0100
  Message-ID: <20111111002533.Horde.mT9jfemkpHVOvF1toqsQ91A@www.retzgen.de>
  From: xxen <hxxg@retxxxn.de>
  To: jule@localhost
  Subject: Nostalgiebox
  User-Agent: Internet Messaging Program (IMP) H4 (5.0.14)
  Content-Type: text/plain; charset=ISO-8859-1; format=flowed; DelSp=Yes
  MIME-Version: 1.0
  Content-Disposition: inline
  Content-Transfer-Encoding: quoted-printable

  H=FCbsch, allerdings sind 10 Euronen f=FCr ne Blechb=FCchse auch nicht von =
Message-Id: <E1ROdzx-0000u7-Po@sxxxerver.info>
From: www-data <xxg@xxx.de>
Date: Fri, 11 Nov 2011 00:25:33 +0100
X-SA-Exim-Connect-IP: <locally generated>
X-SA-Exim-Mail-From: xxing@xxx.de
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
        sxxxxver.info
X-Spam-Level:
X-Spam-Status: No, score=-91.1 required=5.0 tests=AWL,BAYES_00,
        FH_HELO_EQ_D_D_D_D,MISSING_HEADERS,MISSING_SUBJECT,RCVD_IN_PBL,
        RCVD_IN_RP_RNBL,RDNS_DYNAMIC,TO_NO_BRKTS_DYNIP,TVD_SPACE_RATIO,
        USER_IN_WHITELIST autolearn=no version=3.3.1
X-SA-Exim-Version: 4.2.1 (built Mon, 22 Mar 2010 06:26:47 +0000)
X-SA-Exim-Scanned: Yes (on s15xxxserver.info)

schlechten Eltern

http://www.ebay.de/itm/Anzunder-Grillanzunder-Grill-Swissflame-Nostalgiebox=
-/380282752169?pt=3DKaminzubeh%C3%B6r&hash=3Ditem588a9e4ca9

I have noticed that the receiving Server at GMX added its own lines of 
header AFTER the message. (And GMX isn´t the only one). Something in 
the header of horde is missing which signifies the end of the headers. 
When sending via Squirrelmail with the same Exim setup on the same 
server generates Emails without the problem