The solution to this on another forum I'm a part of was to be a lot more liberal with locking threads. For example, once a question was answered or a request was fulfilled the thread was locked to prevent further spamming. This would prevent threads like this and this (which is essentially the exact same topic anyway) from gaining any sort of ground with spam.

You moderate the users, or you remove the paid signatures. While this is a lot easier said than done, I'm hoping that something eventually gets theymos' approval and it can begin to take effect; there's only so much users can do without authority.