@JanDvorak,
"He told me that a car had once almost run him over as he was crossing the street," is a grammatical sentence and conveys the meaning of the first sentence in reported form.
"... that a car had almost run him over as he had crossed the street" isn't grammatical because it coveys the meaning of an action, him having crossed the street, occurring after the car had almost run him over.
"... that when he was crossing ... a car almost ran him over"?
What words are you omitting in the second set of ellipsis? If you mean "he told me that when he was crossing a car almost ran him over," then it is grammatical and conveys the meaning of the first sentence in reported form.