How many deletion stubs are in the notes db? Perhaps you should shorten down the number of day purge interval?
http://www-01.ibm.com/support/docview.wss?uid=swg21095683
Here is a freee utility that can report on how many deletions stubs are in the db and can actually purge them if you want to.
http://www.nsftools.com/tools/delstubs.htm
You also want to see how fragmented the sql db is .