You are reacting to stylistic expectations. That is optional in all four uses. As you add words that can also carry emphasis, it becomes more and more desirable to omit an optional element and thereby reduce the number of words that can be emphasized.
Martin Endley, in Linguistic Perspectives on English Grammar, has a section on optional "that clause complements":
Another striking feature of that clause complements when they function
as DOs (direct objects) is that, under certain conditions, the use of
the complementizer becomes optional and may be omitted without
affecting the grammaticality of the sentence:
(53) a. Dr. Endley knows (that) Ankara gets very cold in the winter.
b. Dr. Endley told his mother (that) Ankara gets very cold in the
winter. (p. 372)
What are the conditions of omission? Endley provides three general guidelines that guide usage:
Register. More formal utterances tend to use that, and spoken English is more likely to omit it.
The importance of information in the clause. If the information is more significant, that is more likely to be used. If the information is mostly descriptive, that is less likely to be used.
Distance between the main verb and the that clause. Close proximity renders the that-clause optional; with more intermediate phrases, the need to emphasize the relation to the main verb with a that-headed clause grows.
Guideline 2 is most relevant to your examples. In (1):
- You said that he would come to the party.
The information is stated in full, and so it can be read as relatively significant. That gives an added bit of emphasis. However, in (4):
- He came to the party, just like you said that he would.
"That he would" is the only part of the clause. The that-clause mainly acts to remind readers that you said information similar to the first part of the sentence. Because the information in this clause isn't otherwise significant, it feels odd to emphasize it with that. 2 and 3 follow similar lines: if 2 feels marginally acceptable, it is only because emphasizing that would be less odd without the added emphasis of just before like or as. In other words, at least in 2 that isn't competing for attention.
Source: Endley, Martin J. Linguistic Perspectives on English Grammar: A Guide for EFL Teachers. Information Age Pub., 2010.