It doesn't do that on all your requests, does it? I thought everyone did that via local bloom table (or similar structure), and checking with a central backend only when it gets a potential hit.
They're still not off the hook for doing autocomplete on the server by default. That effectively gives them every typed in URL.