Based on how people talk and what I see everyday in newspapers and on respectable websites, your second version of the third example is quite acceptable. It is my observation that leaving out the word "that" is a developing trend in the English language. If I remember correctly, when I was in elementary school in the 1960s learning to read and write English, the word "that" was always included. I still include it when I want to be very clear.
I'm looking at your Example 2, the book title The Man Who Mistook His Wife for a Hat. If we remove the word "who," we are making a statement about some event that happened, saying, "The man mistook his wife for a hat." If we insert the word "who," we are talking about "the man" who did this, not making a statement about an event. That's just the way the language works; I'm not sure if I can cite a rule.
Another similar thing I've noticed is "depends" vs "depends on." Wife asks husband, "Can you pick up milk on your way home tonight?" He replies, "It depends if I can come straight home or if have to drop off something at the other end of town."
In earlier times, we would say, "It depends on whether or not..."
As I know, the relative pronoun can only be omitted when it is the
object of the clause; when the relative pronoun is the subject of the
clause, it cannot be omitted.
The difference between "The Land That Time Forgot" and "The Man Who Mistook His Wife For a Hat" is that the first has a clause after "that" and the second does not.
From The Basics of Clauses in English:
Clauses are groups of words that contain a subject and a verb.
The group of words "time forgot" is a clause because it contains a subject "time" and verb "forgot."
"Mistook His Wife For a Hat" does not have a subject; it only has a verb "mistook" and object of the verb "his wife for a hat."
PLEASE NOTE, this answer regards English grammar and the proper usage of the relative pronoun. Neither I nor anyone else suggests that book titles be changed.