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.)
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.