Segmenting the space of certificates so that "partial" CRL can be computed is possible and supported, but it must be done properly. One base principle of CRL is that a CRL should be amenable to processing regardless of how it was obtained: that's the whole point of having signed objects. Since a certificate is considered as non-revoked by virtue of not appearing in the CRL, it must be possible to unambiguously verify whether a given CRL applies to a given certificate or not -- in X.509 terminology, whether the certificate is in scope of the CRL.
The extension to use is
CRL Distribution Points -- see section 220.127.116.11 of RFC 5280. This extension has two distinct roles: it documents URL where CRL may be obtained, and it implements certificate space segmentation. For segmentation (that which you are interested in), the extension must be marked critical, and there must be a match between a "distribution point" and the corresponding structure in the
Issuing Distribution Point extension of the CRL. In effect, each distribution point characterizes a sub-space of the certificate space; each certificate is marked with the sub-space to which it belongs, and each CRL is marked with the sub-space to which it applies. As with all things X.509, details are intricate and some thorough testing is needed in order to assess the reality of support by existing applications.
Such segmentation is useful for keeping CRL size low. It could be used to make single-certificate CRL, although this would have to be balanced with the cost of signing all these CRL (signatures are not expensive, but one million signatures can become a burden -- not really the signatures per se, but all the encoding and file transfer has some overhead).
You cannot expect much privacy gains that way: certificates are inherently public elements, which travel unprotected in many protocols. They cannot be considered secret. There is little more that can be obtained from CRL; actually, a full CRL is already discreet since it talks only about revoked certificates: it says nothing about unrevoked certificates and does not even hint at their existence.
Ultimately, single-certificate CRL already exist but are called OCSP responses.