Mark's generosity in this crisis seems to more than make up for his earlier stinginess.
Should those sentences always be avoided, or are there cases where they are valid?
The only thing that should be avoided is awkwardness. Putting adverbial phrases between the infinitive complementizer to and the infinitive can sometimes be awkward, but it is certainly never ungrammatical or “invalid”. Even the most conservative and staunchest prescriptivist commenters admit that there is nothing inherently ungrammatical about so-called “split” infinitives, which have been attested in all forms of written English for at least seven hundred years.
Indeed, in many cases, putting the adverbial phrase in the intervening position is the only grammatical place to put it, such as in the example in the original poster’s question. There are a couple posts on Language Log discussing these “obligatorily split infinitives”: (“Obligatorily split infinitive”), (“Obligatorily split infinitive in real life”).
Should those sentences always avoided, or are there cases where they are valid?
A native speaker who hasn't been taught that split infinitives are "wrong" will not actually notice anything ungrammatical about "to boldly go where no man has gone before". Thus it is very hard to argue that split infinitives are actually mistakes. According to Fowler's "A Dictionary of Modern English Usage" (link to Wikipedia article), the notion that split infinitives are grammatically wrong originated from an application of Latin grammar (where it isn't even possible to split an infinitive) to English in the eighteenth century.
My own opinion is that there is no need to avoid them. I'd like to refer you to this notes and queries (Guardian newspaper) discussion for more discussion.
A funny quote from Fowler, via the Guardian style guide:
"The English-speaking world may be divided into (1) those who neither know nor care what a split infinitive is; (2) those who do not know, but care very much; (3) those who know and condemn; (4) those who know and distinguish. Those who neither know nor care are the vast majority, and are happy folk, to be envied." (HW Fowler, Modern English Usage, 1926)
Consider this sentence: "The teacher wanted to frequently scold tardy students." Eliminate the split infinitive without completely re-writing the sentence.
"The teacher frequently wanted to scold tardy students."
Does not mean the same thing. The original sentence says that the teacher wanted to scold them many times. The second sentence says that the teacher often thought about scolding them. That is, in the original sentence, on one occasion the teacher thought about scolding many times. The second sentence says that on many occasions the teacher thought about scolding once.
"The teacher wanted to scold frequently tardy students."
Again, not the same. The original sentence says that each time the student is tardy, the teacher wanted to scold him. This sentence says that the teacher wanted to scold them only after they had been tardy many times.
"The teacher wanted to scold tardy students frequently."
Now it's ambiguous whether you mean that she often had the thought that she wanted to scold them, or that she wanted to scold them many times for each offense.
I'm sure you could re-write the sentence to eliminate the split infinitive while retaining the original meaning, but I don't see how to do it without getting much wordier and more awkward.
Any time following a rule creates all sorts of problems, while the only problem created by ignoring the rule is that pedants criticize us for breaking an arbitrary rule, it seems to me that the logical conclusion is that the rule is flawed.
English does not have infinitives. Latin and her derivatives have infinitives, but many languages, if not most, do not. In the jargon of computers, English has a "work-around." By definition, an infinitive is a single word, a form of a verb, that expresses the idea of the verb, but does not express tense, person, mood, number, or anything other than the basic idea of action or being, and is used as a noun in the sentence.
In English, verbs are modified by "prepositions." I put the word in quotation marks, because it is a misnomer. In Latin, prepositions are thus called because they always precede the word they modify, be it a verb or noun. With verbs, they are conjoined. Example: exit = goes out. Notice that in English, the preposition is a postposition. "Out goes" is simply wrong. You don't want to-go. You want-to go. The "to" modifies the first verb, not the second. That's why we contract want-to to wanna and going-to to gonna. If you want-for, you are not expressing desire, but lack -- the meaning changes. Go to it means something different than go for it. English grammar, as taught in our schools, is not English. It's Latin, and it is wrong. This is probably why kids ignore it. The confusion has to do with politics and society, not linguistics. In England, French was the language of kings and Latin was the language of the Church. English was the vulgar language of peasants and commoners. Imposing French and Latin grammar rules reflects the the dominance of Continental languages, but like in life, it feels wrong and unnatural.
So you should never strive-to eliminate split infinitives, because you should never strive-for a goal that does not exist.