What about a time limit on new thread creation?
The spam people thrive on getting their threads up super fast. So if a time limit is imposed, say 5-10 minutes, it would effectively stop them in their tracks. They make the first thread, then try to make the second but can't because it hasn't cleared the time limit. Then by the time they're clear to make the next one, they've already been identified and banned.
There would also be no interference with the actual site posters. How many people realistically make more than one thread within a five minute window?
Worst case scenario, it would slow them down so they don't get all the topics on the front page at the exact same time.