I think you could get a lot closer by framing this as an optimization problem, where you use the full alphabet dictionary, but add a residual prediction which aims to cover as much of the remaining domain name tree as possible weighted by popularity. This tree could then be pre-baked and stored with the same system. This would probably get you p99 0ms even in Australia.

Now the traversal can be done completely via CDN lookups!

It seems like one purpose of an autocomplete box is help you avoid typos, so that makes it less useful.