Below is my solution, formatted to use Jannis' testing classes.

The solution basically recursively calls clean? on the full array of
words, then on the first half and on the second half, then on the
first quarter, the second quarter, the third quarter, etc.  Whenever
clean? returns true, it stops dividing that section of the array. 
(This description is breadth-first, but the algorithm actually runs
depth-first.  Breadth-first is easier to explain, and the final result
is the same.)

I then noticed that we don't really need to make all these calls to
clean?, because we can sometimes deduce what the results will be
without calling clean?.  For example,  if we call clean? on [0...8]
and the result is false, then we call clean? on [0...4] and the result
is true, then we know that clean? on [4...8] must return false, so we
don't need to make this call.

The ordinary recursion is done by the method findBanned(aWords).  When
the above deduction tells us that clean? will return false, we instead
call the method findBannedThereIsOne(aWords).  In the above example we
would call findBannedThereIsOne(aWords[4...8]), and it will skip
calling clean? on aWords[4...8].

(Yes, findBannedThereIsOne is an awkward name, but at least it's
better than findBannedAndWeKnowThereIsAtLeastOne)

When findBannedThereIsOne is called with an array with only one
element, it doesn't need to call clean? at all, because we know this
must be a banned word.

So that findBanned and findBannedThereIsOne only need to deal with
arrays whose size is a power of two, the main routine,
runYourAlgorithm, divides the input array into chunks of these sizes. 
As I'm typing this, it occurs to me that this code might actually run
faster if runYourAlgorithm didn't do this.  I'll give this a try, but
for now I'll post the version that does the chunking.

runYourAlgorithm also handles the case of an empty array, so the other
two routines don't need to handle it.

Here are the results with Jannis' testing classes.  For the times in
seconds, keep in mind that these tests were run on an ancient 500MHz
Pentium III with other work going on at the same time.

Runs:          10
Words:         121430
Banned Words:  3
Average
  Seconds:     0.5561
  Mails:       76
Verified:      10/10
Rebuilt Banned Words

Runs:          10
Words:         121430
Banned Words:  126
Average
  Seconds:     254.4113
  Mails:       1948
Verified:      10/10
Rebuilt Banned Words

Runs:          10
Words:         3930
Banned Words:  29
Average
  Seconds:     12.5187
  Mails:       327
Verified:      10/10
Rebuilt Banned Words

Runs:          10
Words:         125282
Banned Words:  80
Average
  Seconds:     139.9058
  Mails:       1319
Verified:      10/10
Rebuilt Banned Words

Runs:          10
Words:         127367
Banned Words:  10
Average
  Seconds:     1.5328
  Mails:       210
Verified:      10/10
Rebuilt Banned Words


Wayne Vucenic
No Bugs Software
"Ruby and C++ Contract Programming in Silicon Valley"


======================================

class YourAlgorithm < RQ9Algorithm
  def run()
    runYourAlgorithm(@words)
  end

  # Returns an array containing all banned words from aWords
  def runYourAlgorithm(aWords)
    return [] if aWords.empty?

    # Compute the largest power of two <= aWords.size
    powerOfTwo = 1
    powerOfTwo *= 2 while powerOfTwo * 2 <= aWords.size

    # To simplify the logic in findBanned, we always call it with an
    # array whose size is a power of two.
    aBanned = findBanned(aWords[0...powerOfTwo])

    # If we didn't process all of aWords, recursively do the rest
    if powerOfTwo < aWords.size
      aBanned += runYourAlgorithm(aWords[powerOfTwo..-1])
    end

    aBanned
  end

  # Returns an array containing all banned words from aWords
  # aWords.size is a power of 2, and is > 0
  def findBanned(aWords)
    if aWords.size == 1
      @filter.clean?(aWords[0]) ? [] : aWords
    elsif @filter.clean?(aWords.join(' '))
      []
    else
      iSplit = aWords.size / 2
      if @filter.clean?(aWords[0...iSplit].join(' '))
        # There is at least one banned word in 0..-1, but not in 0...iSplit,
        # so there must be one in iSplit..-1
        findBannedThereIsOne(aWords[iSplit..-1])
      else
        # From the test above we know there is a banned word in 0...iSplit
        findBannedThereIsOne(aWords[0...iSplit]) +
findBanned(aWords[iSplit..-1])
      end
    end
  end

  # Returns an array containing all banned words from aWords
  # aWords.size is a power of 2, and is > 0
  # Our caller has determined there is at least one banned word in aWords
  def findBannedThereIsOne(aWords)
    if aWords.size == 1
      # Since we know there is at least one banned word, and since there is
      # only one word in the array, we know this word is banned without
      # having to call clean?
      aWords
    else
      iSplit = aWords.size / 2
      if @filter.clean?(aWords[0...iSplit].join(' '))
        # There is at least one banned word in 0..-1, but not in 0...iSplit,
        # so there must be one in iSplit..-1
        findBannedThereIsOne(aWords[iSplit..-1])
      else
        # From the test above we know there is a banned word in 0...iSplit
        findBannedThereIsOne(aWords[0...iSplit]) +
findBanned(aWords[iSplit..-1])
      end
    end
  end
end