There may very well be something I'm missing here, but I have a suggestion for how to deal with the random prefix attack.
Keep a running count of the number of requests for non-existent subdomains. Once they exceed a certain number in a short period of time, cease to respond to requests for subdomains that aren't already cached as valid.
Example: foo.com, www.foo.com, and mail.foo.com are cached. A flood of requests for (random chars).foo.com starts up. Once this exceeds 100 requests in a minute, all requests for foo.com subdomains are ignored except for foo.com, www.foo.com, and mail.foo.com.
This would still cut off access to infrequently-accessed subdomains, but subdomains with enough traffic to be in the cache would remain reachable.