In phrases of the form "too X to Y" (e.g. "too big to fail"), can "too" ever be replaced by a word such as "exceedingly", e.g. "exceedingly big to fail"? It sounds wrong to me, although "exceedingly big" on its own sounds certainly correct.
If it isn't correct, how else can I express in formal writing that something is "too X to Y" by a large margin? "Much too X to Y" sounds informal.
Too in the too Adj to VP construction is a negative word.
If something is too big to fail, then it's so big that it can't/won't/shouldn't/must not fail.
The negative is part of the meaning; the modal (can, will, should, etc.) is supplied by context.
This is related to the so Adj that S and such NP that S construction, as in
The too construction uses an infinitive VP instead of a whole tensed clause like the so/such construction, but the sense is the same, except for the hidden negative and modal in the too construction.
But they're all idiomatic constructions and don't follow other grammatical rules.
Consequently *exceedingly big to fail doesn't work at all.
Not really. You could extend it to "much too X to Y" or "far too X to Y" as @GEdgar suggested, but any adverbs that might fit lack the comparative nature of "too," which is required for the "to."
The good news is that it's perfectly fine to use even in the most formal circumstances.
I think a re-phrasing works best, such as:
Why? I agree with others here that too X to Y is difficult to re-cast, and it seems that it has become a phrasal of sorts; a familiar saying. Try replacing "cats" in "raining cats and dogs". Just drawing an analogy, not being formal.
You asked for a word -- I don't have one. But you also asked how to express this if another word was not handy. I believe that too X to Y is handy largely because it replaces other constructions which are normally not nearly comfortable enough for common usage.
Perhaps you could use exceedingly if you change to to for, and the final verb to a noun. For example, "...too big to fail..." becomes "...exceedingly large for failure..."
In this case, one might also replace too with unduly. The exaple works better with more sophistocated text, though: "...the task becomes unduly monotonous for continuation; one might better find themselves regurgitating facts with an air of...").
A late answer, but “too big to fail” is a quotation so it loses impact if rephrased.
Per other responses, “so large it cannot be permitted to fail” would be a more formal way of expressing the same thing.
But the “too … to …” construction is completely acceptable in formal writing.
