I see what you mean but allow me to theorycraft a bit more : Changes and removal of packages are considerably more rare than additions and either happens relatively infrequently. This makes cluster wide cache invalidation relatively trivial (it's easy but has scalability issues, and scalability won't be an issue here). Also, when I said "cached" I probably should have said keeping various indexes in memory to facilitate queries. I actually work with systems in a roughly similar technical domain (way different space though, I work on large scale TV systems).

Your other point is definitely the big challenge but that is exactly the main motivation to use hosted CDNs and other hosted services that have solved this challenge for you o a large extent.

I'm almost tempted to have a go at this.