Instead of http://asdoguhwrouyh, they could probe something like http://asdoguhwrouyh.google or anything else in a zone owned by them, so the uncachable traffic would hit only their authoritative name servers and not the root servers.
But then a lying DNS server could easily identify those, and NOT lie about http://*.google -- the reason these requests are entirely random domain names is so they're not easily recognized as probes.
Except that the queries are already totally identifiable as probes in their current form, which is demonstrated in the article.
... only when the delegation for google. is cached.