"Although this is painful for the security community, we can rest assured that infrastructure of the cyber criminals and their secrets have been exposed as well." http://heartbleed.com/

Sounds like they may have scanned the whole internet themselves.

Google reissued their cert on 12 Mar. I assume that is when they discovered it?