Good question. "Te" is a preposition which usually means at or in. It can also be used to mean too, as in Te veel, or Too much or Te goed, meaning Too good. In other instances, I think its use is highly idiomatic, for example, Dat is niet te vervangen, meaning That is not replaceable, Het is toch te gek, meaning It is just too crazy, Het is niet te doen, meaning It is not doable, and lastly We moeten te werk, meaning We have to (go to) work. This one is very colloquial, as proper Dutch is We moeten naar werk. I can't think of any sentence where one would use" ...moeten te zijn."
Your examples are quite different in their usage of "te".
te in "te gek" = English too; te in "niet te vervangen, niet te doen" = te + infinitive, a bit comparable to English to + infinitive
It's not as if using te is very idiomatic. It's just a preposition with different meanings and functions. To read more on this subject, see https://www.dutchgrammar.com/en/?n=Verbs.Au06.
Finally "we moeten te werk" is not commonly (or never?) said in Dutch. And "we moeten naar werk" doesn't sound very correct in my (native Dutch) ears. The common way of saying this would be "we moeten naar het werk, ik moet naar mijn werk". Of "we moeten aan het werk", but that has a different meaning (we have to start working).
Finally, "moeten te zijn" is indeed incorrect, in general. I could find one example of this word combination though, albeit in a different construction than the sentence here: "factoren die geacht moeten te zijn verdisconteerd in het beleid" = something like "factors which are expected to have been integrated in the policy".