And now, I have a perfectly reproducible case: trying to delete the last mail 
in my inbox results in a crash without the message being deleted. Start up 
KMail again, hit "Delete", crash again :)

Backtrace:

Using host libthread_db library "/lib/tls/libthread_db.so.1".
[Thread debugging using libthread_db enabled]
[New Thread 1110233888 (LWP 6959)]
[KCrash handler]
#3  0x41cd84be in QGDict::look_string () from /opt/qt-3/lib/libqt-mt.so.3
#4  0x401df833 in KMHeaders::msgRemoved (this=0x81e7540, id=136214040, msgId=
      {static null = {static null = <same as static member of an already seen 
type>, d = 0x804e070, static shared_null = 0x804e070}, d = 0x83b62f8, static 
shared_null = 0x804e070}, strippedSubjMD5=
      {static null = {static null = <same as static member of an already seen 
type>, d = 0x804e070, static shared_null = 0x804e070}, d = 0x833ba78, static 
shared_null = 0x804e070}) at qdict.h:73
#5  0x401ea954 in KMHeaders::qt_invoke (this=0x81e7540, _id=-1073750304, 
    _o=0xbfffdf90) at qucom_p.h:388
#6  0x41a1e0fc in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#7  0x40218382 in KMFolder::msgRemoved (this=0x815e2e0, t0=31516455, t1=)
    at kmfolder.moc:227
#8  0x40218c57 in KMFolder::qt_emit (this=0x815e2e0, _id=-1073749984, 
    _o=0xbfffe0d0) at qucom_p.h:388
#9  0x41a1e131 in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#10 0x4023bba2 in FolderStorage::msgRemoved (this=0x815d638, t0=31516455, t1=)
    at folderstorage.moc:224
#11 0x40238f4c in FolderStorage::take (this=0x815d638, idx=3187)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/folderstorage.cpp:406
#12 0x402c9e7d in KMFolderImap::take (this=0x815d638, idx=3187)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmfolderimap.cpp:523
#13 0x40216151 in KMFolder::take (this=0x0, idx=31516455)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmfolder.cpp:312
#14 0x402e3726 in KMFolderMaildir::addMsg (this=0x8183b68, aMsg=0x85de1d0, 
    index_return=0xbfffe3f8)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmfoldermaildir.cpp:425
#15 0x402387a0 in FolderStorage::reallyAddMsg (this=0x8183b68, aMsg=0x85de1d0)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/folderstorage.cpp:292
#16 0x4023c385 in FolderStorage::qt_invoke (this=0x8183b68, _id=3, 
    _o=0xbfffe4e0) at qucom_p.h:312
#17 0x4039fbdd in KMFolderIndex::qt_invoke (this=0x8183b68, _id=3, 
    _o=0xbfffe4e0) at kmfolderindex.moc:87
#18 0x402e8afd in KMFolderMaildir::qt_invoke (this=0x1e0e727, _id=31516455, 
    _o=0x1e0e727) at kmfoldermaildir.moc:77
#19 0x41a1e0fc in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#20 0x403a792a in KMail::FolderJob::messageRetrieved (this=0x87e23d0, 
    t0=0x1e0e727) at folderjob.moc:129
#21 0x403b2db3 in KMail::ImapJob::slotGetMessageResult (this=0x87e23d0, 
    job=0x18f4) at /usr/src/KDE/kde-cvs/kdepim/kmail/imapjob.cpp:403
#22 0x403b46fa in KMail::ImapJob::qt_invoke (this=0x87e23d0, _id=2, 
    _o=0xbfffe6d0) at qucom_p.h:312
#23 0x41a1e0fc in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#24 0x40f3cc7a in KIO::Job::result () from /opt/kde-3/lib/libkio.so.4
#25 0x40f22edc in KIO::Job::emitResult () from /opt/kde-3/lib/libkio.so.4
#26 0x40f249ee in KIO::SimpleJob::slotFinished ()
   from /opt/kde-3/lib/libkio.so.4
#27 0x40f2876e in KIO::TransferJob::slotFinished ()
   from /opt/kde-3/lib/libkio.so.4
#28 0x40f3ec5d in KIO::TransferJob::qt_invoke ()
   from /opt/kde-3/lib/libkio.so.4
#29 0x41a1e0fc in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#30 0x41a1df24 in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#31 0x40f1801e in KIO::SlaveInterface::finished ()
   from /opt/kde-3/lib/libkio.so.4
#32 0x40f150a2 in KIO::SlaveInterface::dispatch ()
   from /opt/kde-3/lib/libkio.so.4
#33 0x40f14280 in KIO::SlaveInterface::dispatch ()
   from /opt/kde-3/lib/libkio.so.4
#34 0x40f11078 in KIO::Slave::gotInput () from /opt/kde-3/lib/libkio.so.4
#35 0x40f139c8 in KIO::Slave::qt_invoke () from /opt/kde-3/lib/libkio.so.4
#36 0x41a1e0fc in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#37 0x41a1e25d in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#38 0x41d61cb2 in QSocketNotifier::activated ()
   from /opt/qt-3/lib/libqt-mt.so.3
#39 0x41a3a7e0 in QSocketNotifier::event () from /opt/qt-3/lib/libqt-mt.so.3
#40 0x419c1c2f in QApplication::internalNotify ()
   from /opt/qt-3/lib/libqt-mt.so.3
#41 0x419c122e in QApplication::notify () from /opt/qt-3/lib/libqt-mt.so.3
#42 0x41549b23 in KApplication::notify () from /opt/kde-3/lib/libkdecore.so.4
#43 0x419b16aa in QEventLoop::activateSocketNotifiers ()
   from /opt/qt-3/lib/libqt-mt.so.3
#44 0x4196b233 in QEventLoop::processEvents () 
from /opt/qt-3/lib/libqt-mt.so.3
#45 0x419d3f98 in QEventLoop::enterLoop () from /opt/qt-3/lib/libqt-mt.so.3
#46 0x419d3e48 in QEventLoop::exec () from /opt/qt-3/lib/libqt-mt.so.3
#47 0x419c1e81 in QApplication::exec () from /opt/qt-3/lib/libqt-mt.so.3
#48 0x0804a734 in main (argc=31516455, argv=0x1e0e727) at kapplication.h:217

Hope this helps.

Oh, and some last insights: pressing Shift-Delete removed the message 
successfully (i.e., do not move it to Trash but rather really delete it).

My inbox is on a local imap server, only the trash is a maildir mailbox local 
to KMail.

Michael, can you check if those crashes still appear in head. I just checked in a fix for a recently introduced imap move crash.

CVS commit by burghard: 

Add a crashguard. Hope this helps.
CCMAIL: 82491@bugs.kde.org


  M +2 -1      kmheaders.cpp   1.638


--- kdepim/kmail/kmheaders.cpp  #1.637:1.638
@@ -1295,5 +1295,6 @@ void KMHeaders::msgRemoved(int id, QStri
     // Remove the message from the list of potential parents for threading by
     // subject.
-    if (mSubjThreading && mSubjectLists[strippedSubjMD5])
+    if (!strippedSubjMD5.isEmpty() && 
+        mSubjThreading && mSubjectLists[strippedSubjMD5])
         mSubjectLists[strippedSubjMD5]->remove(removedItem->sortCacheItem());
 

Nope, still can't delete mail at all anymore, the console debug output is:

kmail: KMFolderImap::slotCheckValidityResult of: INBOX
kio_imap: IMAP4::dispatch - command=77
kio_imap: IMAP4Protocol::special
kio_imap: URL: box= INBOX, section= , type= , uid= 4444, validity=
kio_imap: IMAP4::parseURL: box INBOX
kio_imap: IMAP4::parseURL - return 4
kio_imap: IMAP4Protocol::assureBox - reusing box
kio_imap: IMAP4::dispatch - command=71
kio_imap:  IMAP4::listDir - newimap://michael@localhost:143/INBOX/;SECTION=UID 
FLAGS
kio_imap: URL: box= INBOX, section= UID FLAGS, type= , uid= , validity=
kio_imap: IMAP4::parseURL: box INBOX
kio_imap: IMAP4::parseURL - return 2
kio_imap: IMAP4Protocol::assureBox - reusing box
kio_imap: IMAP4: select returned:
kio_imap: Recent: 0d
kio_imap: Count: 3196d
kio_imap: uidValidity: 1082195311d
kio_imap: Flags: 63d
kio_imap: PermanentFlags: 95d
kio_imap: Access: Read/Write
kio_imap: IMAP4Protcol::listDir - Finishing listDir
kmail: processNextCheck, remaining 0
kmail: account newton finished check
kio_imap: IMAP4::dispatch - command=67
kio_imap: IMAP4::get -  
newimap://michael@localhost:143/INBOX/;UID=4445;SECTION=BODY.PEEK[]
kio_imap: URL: box= INBOX, section= BODY.PEEK[], type= , uid= 4445, validity=
kio_imap: IMAP4::parseURL: box INBOX
kio_imap: IMAP4::parseURL - return 5
kio_imap: IMAP4Protocol::assureBox - reusing box
kio_imap: imapParser::parseBody - discarding 4445
kio_imap: IMAP4::get -  finished
*** KMail got signal 8 (Crashing)
KCrash: crashing... crashRecursionCounter = 2

and the backtrace:

Using host libthread_db library "/lib/tls/libthread_db.so.1".
[Thread debugging using libthread_db enabled]
[New Thread 1110377248 (LWP 30606)]
[KCrash handler]
#3  0x41cfb4be in QGDict::look_string () from /opt/qt-3/lib/libqt-mt.so.3
#4  0x401e6800 in KMHeaders::msgRemoved (this=0x846c318, id=138855408, msgId=
      {static null = {static null = <same as static member of an already seen 
type>, d = 0x804e070, static shared_null = 0x804e070}, d = 0x822edf0, static 
shared_null = 0x804e070}, strippedSubjMD5=
      {static null = {static null = <same as static member of an already seen 
type>, d = 0x804e070, static shared_null = 0x804e070}, d = 0x86f3b90, static 
shared_null = 0x804e070}) at qdict.h:73
#5  0x401f1b77 in KMHeaders::qt_invoke (this=0x846c318, _id=-1073748912, 
    _o=0xbfffe500) at qucom_p.h:388
#6  0x41a410fc in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#7  0x4021f602 in KMFolder::msgRemoved (this=0x8187ba0, t0=161323367, t1=)
    at kmfolder.moc:227
#8  0x4021fed7 in KMFolder::qt_emit (this=0x8187ba0, _id=-1073748592, 
    _o=0xbfffe640) at qucom_p.h:388
#9  0x41a41131 in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#10 0x40242e22 in FolderStorage::msgRemoved (this=0x8187d70, t0=161323367, 
t1=)
    at folderstorage.moc:224
#11 0x402401cc in FolderStorage::take (this=0x8187d70, idx=3194)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/folderstorage.cpp:406
#12 0x402d110d in KMFolderImap::take (this=0x8187d70, idx=3194)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmfolderimap.cpp:523
#13 0x4021d3d1 in KMFolder::take (this=0x0, idx=161323367)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmfolder.cpp:312
#14 0x402ea9b6 in KMFolderMaildir::addMsg (this=0x81b01b0, aMsg=0x86dfa00, 
    index_return=0xbfffe9f8)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmfoldermaildir.cpp:425
#15 0x40240caa in FolderStorage::moveMsg (this=0x81b01b0, aMsg=0x86dfa00, 
    aIndex_ret=0x99d9967)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/folderstorage.cpp:536
#16 0x4021d5d8 in KMFolder::moveMsg (this=0x0, msg=0x99d9967, 
    index_return=0x99d9967)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmfolder.cpp:357
#17 0x40378d59 in KMMoveCommand::execute (this=0x8721ad0)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmcommands.cpp:1738
#18 0x4036fe6d in KMCommand::slotPostTransfer (this=0x8721ad0, result=OK)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmcommands.cpp:190
#19 0x40369644 in KMCommand::qt_invoke (this=0x8721ad0, _id=4, _o=0xbfffec60)
    at qucom_p.h:312
#20 0x4036d48d in KMMenuCommand::qt_invoke (this=0x99d9967, _id=161323367, 
    _o=0x99d9967) at kmcommands.moc:2414
#21 0x4036d8c1 in KMMoveCommand::qt_invoke (this=0x8721ad0, _id=4, 
    _o=0xbfffec60) at kmcommands.moc:2581
#22 0x4036db1d in KMDeleteMsgCommand::qt_invoke (this=0x99d9967, 
    _id=161323367, _o=0x99d9967) at kmcommands.moc:2656
#23 0x41a410fc in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3
#24 0x403694ca in KMCommand::messagesTransfered (this=0x8721ad0, t0=OK)
    at kmcommands.moc:120
#25 0x4036febd in KMCommand::transferSelectedMsgs (this=0x8721ad0)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmcommands.cpp:210
#26 0x4036fcab in KMCommand::slotStart (this=0x8721ad0)
    at /usr/src/KDE/kde-cvs/kdepim/kmail/kmcommands.cpp:182
#27 0x4036962d in KMCommand::qt_invoke (this=0x8721ad0, _id=3, _o=0xbfffeef0)
    at kmcommands.moc:140
#28 0x4036d48d in KMMenuCommand::qt_invoke (this=0x99d9967, _id=161323367, 
    _o=0x99d9967) at kmcommands.moc:2414
#29 0x4036d8c1 in KMMoveCommand::qt_invoke (this=0x8721ad0, _id=3, 
    _o=0xbfffeef0) at kmcommands.moc:2581
#30 0x4036db1d in KMDeleteMsgCommand::qt_invoke (this=0x99d9967, 
    _id=161323367, _o=0x99d9967) at kmcommands.moc:2656
#31 0x41a410fc in QObject::activate_signal () from /opt/qt-3/lib/libqt-mt.so.3

Thanks,
  Michael

Aha, thanks Till! After deleting the index the crash disappeared, cool. I'll 
take the opportunity to close the bug, thanks for fixing it! :)