We all have a lot of internal services that need encryption and authentication to be provided by some sort of PKI.
Do the security gains of using a different private/public key pair for each service justify the extra work entailed?
Or is using a single key pair per server Good Enough?
For instance, all of my *nix servers have rsyslog, Bacula, and Puppet running on them. Does using a common, server-specific key pair across all three services open up an attack vector I'm overlooking?
The more ciphertext that's available, the easier it is to crack. Having said that, all security is a trade off. You need to think what are you using the certificates for? Encryption? Authentication? What would happen if there was a compromise? How does that weigh against the administration benefit of having less certificates to keep track of. You're using puppet, so some of the administrative overhead is reduced.
We use a custom root certificate and a single wildcard keypair where possible on our internal systems. This is mostly just to stop casual sniffers gaining passwords. I'm sure that a determined hacker would find a way in. Having just had our certificate expire, we've set up puppet infrastructure to distribute the key and restart services. Next year we just need to check the new keys into subversion and puppet should do the rest.
*For instance, all of my nix servers have rsyslog, Bacula, and Puppet running on them. Does using a common, server-specific key pair across all three services open up an attack vector I'm overlooking?
I've not had the pleasure (pain?) of deploying a PKI, but I've dealt with certificates. I suspect per-server will be fine as long as the encryption you're using is of high quality (i.e. not an older method prone to attack and using a good length key).
I think you would be best off having one per server. If you're in an environment where you're pretty sure the compromise of one service won't lead to access to the keys of others on a single server, then per server per service.
The overhead of managing those extra keys shouldn't be too bad. What you gain is the knowledge that some compromised service (say, Bacula) won't allow the attacker to compromise Puppet transactions. Is that worth it? Maybe, but only if you can assure yourself that someone breaking into a service can't just get the keys from those other services anyway.