There is a terrible answer here, which is that you make users of PackageKit swallow a scheduled job that keeps all metadata fresh. Every few hours it just pulls down every single bit of metadata out there (think apt-get --update). That way whenever you go to use PackageKit, 9 times out of 10 you have the latest metadata and there is no need to go download anything new. And if there is a repo that is out of date (and we already have ways of discovering this very quickly/easily) the amount of new stuff to download will be quite small as compared to downloading for every repo.
There is a terrible answer here, which is that you make users of PackageKit swallow a scheduled job that keeps all metadata fresh. Every few hours it just pulls down every single bit of metadata out there (think apt-get --update). That way whenever you go to use PackageKit, 9 times out of 10 you have the latest metadata and there is no need to go download anything new. And if there is a repo that is out of date (and we already have ways of discovering this very quickly/easily) the amount of new stuff to download will be quite small as compared to downloading for every repo.