This answer is based on the intuition I have long held: genitives like nostrum and vestri are not forms of the personal pronouns nos and vos, but of the substantivized possessive adjectives.
I have no sources to back this up, but I am posting these thoughts here for scrutiny.
Some pronouns (ego, tu, nos, vos, se) have an associated possessive pronoun (meus, tuus, noster, vester, suus) that takes some of the functions of the genitive.
Therefore the role of the genitive is not directly comparable to nouns and most pronouns.
These special pronouns do not have a genitive form in the completely usual sense.
My intuition has always been that sui, nostri, vestri and the like are singular genitives of the substantivized neuter adjective suum/nostrum/vestrum.
Thus, sui/nostri/vestri/mei/tui are not forms of the personal pronouns themselves, but rather of the related possessive pronoun.
The putative noun nostrum is almost synonymous with res nostra, so you could read nostri as rei nostrae.
Notice that it is irrelevant that nos is plural; the possessive adjective noster is only used in the singular here.
Therefore the -i you see is a singular genitive ending, and the connection to plural comes from the meaning of the word noster.
This reasoning does not extend to all uses of the genitive as such, but the same principle applies.
For partitive genitive, you always have nostrum/vestrum — at least I have never seen nostri/vestri partitively.
For example, "one of us" would be unus nostrum, which I read roughly as unus virorum nostrorum.
Again, noster is substantivized, and here means "a man from our group".
The shorter genitive plural ending -um instead of -orum is possible for many words, and nostrum and vestrum sound just like the kind of thing that I expect to wind up having the shorter variant.
Of course, these genitives of the possessive pronouns can start a life of their own and obtain new uses by analogy.
See this question, for example.
Most instances of nostrum/vestrum used a possessive genitive actually make sense when parsed as plural genitives of a substantivized possessive pronoun.