What would happen if a spammer intentionally starts putting hundreds of different invisible random URIs within the message trying to DoS SURBL?
I can't speak for the plugins you mention, but in my implementation I look exclusively for visible URIs and ignore all others. Then, having such a high number of URIs would definately be an excellent criteria to flag the message as spam just because of this.
IMHO blocking on spamvertised URIs is the most effective aproach to the problem. There is really no way out - not even your scenario provided the server is propperly implemented. We have a local database of spamvertised domains on our server and therefore the performance drawback would not really matter that much. This database is then updated every now and then which obviousely generates less traffic.
Markus