After fours years of working with Baan support on this problem they've finally come up with a solution that works. Its a bit unorthodox (since they do not support customizations) but I thought that there may be other customers out there who has encountered the same problem.
Solution :
Add an index to the tables
Each of the following tables needs a new index on fields item (Item) and cntr (Container), flag duplicates allowed should be set to yes:
tdpur041
tdpur051
tdsls041
tdsls051

Time to delete has dropped from 8 hrs/item to 3 mins/item

Does this only work when you are using a level 2 database driver? Would the same time reduction occur if a level 1 driver was used?

I can't say. We are only using level 2 drivers so I cannot compare with level 1.