In Japanese, 彼の車は私と同じです is a perfectly natural sentence. When you compare two things, this type of omission* is extremely common in Japanese, and it can be found even in the most formal writings.
(* This may seem to be "omission" from the English perspective, but Japanese people may say nothing is omitted.)
Examples:
彼の英語は私より上手です。
His English is better than mine.
地球の体積は月より大きい。
The volume of the earth is larger than that of the moon.
この店で売られているリンゴはあの店より美味しい。
Apples sold at this store are more delicious than those sold at that store.
彼の考えは君とは違う。
His opinion is different from yours.
限定版の値段は通常版と同じです。
The price of the limited edition is the same as that of the regular edition.
(Actually "His car is the same as me" is a common mistake made by Japanese students.)
If there were not many examples of 私のと同じ, it's probably because 私の is relatively colloquial, and in speech の tends to be "omitted" anyway. Instead of の, you can use the stiffer pronoun (の)それ and say the following:
- 彼の車は私の車と同じです。
彼の車は私のそれと同じです。
- 地球の体積は月の体積より大きい。
地球の体積は月のそれより大きい。
But sentences like these are found mainly in strict technical documents or translated materials. You can (or should) stick to the shorter versions in most cases.
EDIT: Of course you have to avoid "omission" when it causes confusion:
- 君のお父さんは僕のお父さんより背が高い。
Your father is taller than my father.
- 君のお父さんは僕より背が高い。
Your father is taller than me.