This bug seemed to have been fixed about one year ago, but has reappeared since upgrading to KDE 3.5.9 / kmail 1.9.9. Also, now some messages indeed present on the server do not appear in the message list. I have reported these problems upstream. http://bugs.kde.org/show_bug.cgi?id=159453