I agree with the case for using a wildcard, but just to play devil's advocate - why can't they take the CloudFlare approach?
Generate a cert for 100 of your client's domains, use that cert across those domains. Cut your 50m domains down to 500,000 certificates. Serving the right certificate for the right domain is a simple enough task.
As new tumblr domains are registered, generate more certs in batches of 100 domains.
I doubt anyone would ever seriously suggest putting millions of SANs on a single certificate, but 100 isn't too farfetched.