The "birthday problem" calculates the odds of ANY TWO addresses in a set matching EACH OTHER.
Unless I'm misunderstanding gmaxwell's post, he's talking about ONE address in a set (the work) matching a specific given address (the contract).
I'm sorry if I was unclear. You are not provided with an address. You are provided with a public key. Now you construct many possible addresses looking for a pair where one is a plausible contract and the other lets you spend all the coins.
You show your counterparty one, then spend with the other.