How to do AB Testing using Google Website Optimizer

Thanks, I take that as a compliment :)

we integrate with GWO before there was Visual Website Optimizer or Optimizely. Believe me, i'd love to undo that decision.

This problem is well known in optimization. The A/B testing approch, when use correctly, provides a local optimization method that will bring you closer to the local maxima (or minima by inverting the metric sign). Note however that it is not the most efficient.

To locate the global maxima, if you have no prior knowledge on the underlying function, you have to pick very different starting points and apply the local optimization algorithm. The starting points may be picked at random, or in a grid for complete scanning or preferably using some priori knowledge which we do have on web services efficiency.

I thought that part of the video was bullshit. I thought the same when Atwood wrote his "Groundhog Day" piece, which the video seems to accept at face value.

A/B testing lets you test two competing hypotheses. It does not in any way require that the two hypotheses be very similar to each other. You can test radically different designs against each other just as easily as you can test minor differences.

So, the real question you are asking is: how do you generate new hypotheses? And the answer is: the same way as always. You can see what other are doing. You can think "out of the box." You can use your best judgment, and whatever creativity you have access to.