K3b is really slow handling large amounts of files. I have like 30,000 files in one directory in a project. I told K3b to remove some 2,000 of them because they do not fit. K3b has been running for 20 min at full CPU speed and the GUI does not even update meanwhile.
Adding files is manageable but removing files is a nightmare.

This sounds like a bug from what I can tell. If you try to remove an entire folder (which contains a large number of files) does this operation complete quickly?