Unfortunately the problem isn't necessarily with PayPal itself, the larger problem is how DNS is handled. Because the attack was on their DNS provider, any recursive servers that cache the results only can cache them until the TTL expires. Even if the upstream reports SERVFAIL or does not respond, they then start to return SERVFAIL or NXDOMAIN for the site.
One way to fix this is to not drop entries upon TTL expiration IFF the upstream server returns SERVFAIL or does not respond. Alternatively, DNS pinning might not be a bad idea for entries that don't charge often.
I had a issue with paypal around that time but thats the only downtime ive had for the years ive been using them. Every company cant be expected to be up 100% of the time.