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”).
A native speaker who hasn't been taught that split infinitives are "wrong" will not actually notice that there is something 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:
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.