OK, to debug further can you please run this using the latest GIT code: valgrind --tool=callgrind kmail --nofork immediately exit kmail, and send me the generated callgrind.out.<pid> file? I can then use that file to analyze the execution of the code on your machine and see if there is another suboptimal codepath in use.
At least the numbers are now generally within 1/2 second of the original numbers...
kmail: http://humanreadable.nfshost.com/trinity/build_logs/callgrind.out.574
konqueror: http://humanreadable.nfshost.com/trinity/build_logs/callgrind.out.19425
kate: http://humanreadable.nfshost.com/trinity/build_logs/callgrind.out.21982
Darrell