The spam cleaner is for manual removal of spam messages, it's not for detection of spam. There are other settings in Spam Management in the ACP for that which you need to check and set.
I also suggest you look at the flood check settings. The default is 30 seconds, which is fine. You should also check the permissions you have set for this - really you should have bypass flood check set to Not Set (No) and not Allow. If users can't bypass the flood check then they can only make 1 post every 30 seconds. Your spammers made 4000 posts, let's say that's 1000 posts each. That would take them a minimum of 500 minutes or 8 hours 20 minutes of solid sitting and continually posting with no break, which I can't quite believe. If you allowed the flood check to be bypassed in permissions or have set the timing too low, then they will have made these posts a lot quicker.