For example, an ISP or government capable of tracking millions of keys being exchanged. Would that provide a sample large enough to be able to identify the private key on either end?
Examining public keys gives you no insight, no matter how many you see, that would allow you to derive the private from the public key.
Yes and no.
Earlier this year a research paper was published that discovered a flaw with RSA crypto keys where if (and this is a MAJOR simplification) you found two certificates that shared a prime number you could use some math to find out the missing prime number from both certificates.
As you can tell this caused quite a stir in the various News Media. However it is not as bad as it seems. This only happens if you have a low entropy random number generator and the only commonplace location you will find them are certificates in embedded devices (like your router or firewall).
Freedom To Tinker posted a very good followup article explaining why this is not as bad as everyone first thought.
In the simplest terms, if you want to protect your self make sure you have a good random number generator with a high entropy source and allowing for entropy to build up in between generating your
Each private key has one and only one public key. Anyone, regardless of resources could get access to many public keys as they are designed to be shared and in-fact, the whole system depends on the easy availability of public keys for a given private key.
To explain it another way, the purpose of a public key is simply to allow someone to know that the person they are communicating with holds the private key that corresponds to it. It can also be used to send information to the holder of the private key such that only they can decrypt the message.
The two keys are mathematically related and any change to one would require the other to change, so it isn't even possible to have a system with multiple public keys for the same private key, nor would there be any security benefit in it since public keys are not secret.