How about just using unique addresses for every transaction from the start? Using a payment protocol (such as the one being developed), the problem of address reuse goes away entirely.

I agree that for some cases, like anonymous donations, where you don't want any out-of-band communication to occur a scheme such as this would be nice.