I'd long been puzzled by the fact that Clemenza and Rocco just left the cadaver behind on an open road after shooting Paulie in The Godfather. But if the Corleones wanted the death of the traitor to send a message to the other families, it makes sense that they would want his body to be found with the bullet in the head, so as to remove any ambiguity.
Naturally, they'd want the other families to know but not the civil authorities. So how did they rig things so that the car would not be traced back to them by the police? I don't recall this being explained in the film (and unless I missed something, the book doesn't explain it, either, a fact I found very odd since the book details Clemenza cogitating over and over about how to pull off the execution just perfectly and not arouse his turncoat protégé's suspicions).