As Peter pointed out, I was using GNUPG command-line terminology. However, it seems we are talking about the same thing.I'm not familiar with this term "throw-keyid". We don't use it in RFC2440-bis as far as I know. I think however that you are referring to this feature discussed in section 5.1: An implementation MAY accept or use a Key ID of zero as a "wild card" or "speculative" Key ID. In this case, the receiving implementation would try all available private keys, checking for a valid decrypted session key. This format helps reduce traffic analysis of messages.
That does seem to be a valid attack against the anonymity. However you should be aware that OpenPGP is not trying to provide very strong anonymity here. No effort is made to obfuscate the key size, for example, so unusually sized keys tend to reveal themselves. All the RFC phrasing suggests or claims is that it can "help reduce" traffic analysis. If we really wanted to guarantee strong anonymity I think we would have to do quite a bit more work here. Your attack is definitely something to consider. However, strong anonymity is not something we have aimed to provide. Given the weak level of anonymity it affords, perhaps the zero keyid feature is misleading to users? If so, should we consider deprecating it until we are willing to do the work necessary to do the job right? Or we could at least put a note in the RFC emphasizing that this feature does not provide strong anonymity and should not be relied upon for that purpose.
Yes, there are certainly other issues in anonymity. Even if two keys are the same number of bits there could be attacks. E.g. If 110000001 and 100000001 were both primes used for different ElGamal keys and adversary would still have a significant advantage in distinguishing the receiver. Having common ElGamal NIST primes would take care of this and have the small benefit of faster key generation. This is discussed in a Bellare paper: http://www-cse.ucsd.edu/users/mihir/papers/anonenc.html . The thing unique about the attack I described is that no one has considered a definition "Key-Privacy" in the multiple recipient case. However, I believe a solution from "commodity parts" can be made.
As far as whether it is a problem, I believe that Hushmail uses such feature to implement BCC functionality. Also, I PGP is used in some other contexts such as newsgroups like alt.anonymous. In short it seems that some applications might rely on the feature whether it was intended to be strong or not.
In the short term it might help to serve notice in some way. Perhaps a note of the RFC would be good. While there does seems to be a bit of work to do, it seems feasible to implement the feature properly. My opinion is that eventually it would probably be best to either provide the feature fully or remove it. Which one to do probably depends on what goals of PGP are.
-Brent