As of 4.10.4 this bug has returned for me.
However restarting kontact does "fix" the problem, although it's only temporary.

* 781029 SEARCH (UID 781029 REV 1 REMOTEID "6tO1Qx97GY.vcf" MIMETYPE "text/directory" COLLECTIONID 128 SIZE 145 DATETIME "10-Jul-2013 10:23:12 +0000" FLAGS () PLD:RFC822 {145} BEGIN:VCARD EMAIL:e.g@c.com FN:E G N:G;E;;; NAME:E G UID:6tO1Qx97GY VERSION:3.0 END:VCARD ) 
1956 OK SEARCH completed 
1957 SEARCH "SELECT DISTINCT ?r ?reqProp1 WHERE { ?r <http://akonadi-project.org/ontologies/aneo#akonadiItemId> ?reqProp1 . ?r nco:nickname \"e.g@c.com\"^^<http://www.w3.org/2001/XMLSchema#string> . }" FULLPAYLOAD EXTERNALPAYLOAD (UID REMOTEID REMOTEREVISION COLLECTIONID FLAGS SIZE DATETIME) 1958 X-AKAPPEND 12 0 (\MimeType[message/rfc822] $QUEUED $SIGNED) ("PLD:HEAD[1]":441,"PLD:ENVELOPE[1]":200,"PLD:RFC822[1]":5709,"ATR:AddressAttribute":122,"ATR:TransportAttribute":10,"ATR:SentActionAttribute":4,"ATR:DispatchModeAttribute":11,"ATR:SentBehaviourAttribute":8) {6505} 
1957 OK SEARCH completed 
1958 X-AKAPPEND 12 0 (\MimeType[message/rfc822] $QUEUED $SIGNED) ("PLD:HEAD[1]":441,"PLD:ENVELOPE[1]":200,"PLD:RFC822[1]":5709,"ATR:AddressAttribute":122,"ATR:TransportAttribute":10,"ATR:SentActionAttribute":4,"ATR:DispatchModeAttribute":11,"ATR:SentBehaviourAttribute":8) {6505} 
+ Ready for literal data (expecting 6505 bytes) 
1958 NO Append failed 


+++ This bug was initially created as a clone of Bug #285945 +++

Version:           4.7 (using KDE 4.7.3) 
OS:                Linux

When I try to send a mail the composer stalls for a while and then displays "There were problems trying to queue the message for sending: Append failed".
Restarting akonadi, kde or the whole pc did not help.
The Mail is not even saved in drafts. No Error is shown but after a restart the message is gone.