First of all, thank you for your answer!

Yes, this is how I see it working. It may be slightly inefficient but it is the only reliable method.

Yes, and that is the part that does not work when two devices with different app sets share the same account.

No, that was not what I meant. I do realize the information leakage problem which is why I was not considering that scenario. I was assuming the "give me the full list with versions and I will choose" case. Yes, there is a potential for a performance hit as seen on e.g. the N900 but that can be alleviated.

Debian based systems are plagued by the fact that each time the catalogues are refreshed, the whole shebang with the dependencies is transferred (up to about 10MB per repository in Maemo's case) and parsed. One way to reduce that is to split it in two parts: 1) names and versions, 2) dependencies. That way, the difficult part (parsing the dependencies) would be done only for the specific package the user selects for installation or upgrade and only when he choses to do so.

Please note that there is still an information leakage ("Johny is installing package X"), but only to the repository that provides that package and that is unavoidable anyway.