gmaxwell,

I have a lot of respect for your knowledge in this area, so I'm pretty sure I'm the one who still isn't understanding.

Edit: Perhaps I am beginning to understand?  By the time I finished writing this post I realized that the 2-set method might not be as difficult as I thought.  My initial assumption (in my earlier post) was 1 address in one set, and multiple addresses in the other set until there was a collision with the single-address set. As I wrote this post it dawned on me that it might be more efficient to generate equal numbers of addresses in each set until one set collided with the other.

Using the public key that I'm provided with, I can generate MANY plausible contracts until two of them collide with each other.  However, this isn't useful, since I won't be able to use either to spend the coins.

I could also generate MANY addresses that let me spend all the coins until two of them collide with each other.  However, this isn't useful, since I won't be able to show my counterparty either of them.

After some thought, I suppose I'd need to generate 2 sets.  I can generate MANY addresses in one set that let me spend all the coins , and then generate MANY plausible contracts in the other set.  I'd have to continue this until an address in set 1 collides with an address in set 2.

I'm not 100% certain on the maths, but (depending on how much more effort the contract generation requires) while that seems to require less effort than my initial example (where the "plausible contracts" set only has 1 address), it would seem to require more effort than the "birthday problem".  My intuition is that on average it requires twice as many P2SH addresses to be generated as the "birthday problem" would (since each new address in one set is effectively a new potential match in the other set)?  If that's right, then I suppose that means it's just one extra "bit" of security over the birthday problem?