Sorry, I didn't qualify "always feasible" well enough. What I meant was, I want it to be feasible to reason about the halting states of every single smart-contract that will ever interact with my code. Not just the ones that I write, but also the ones that are reachable from my smart contract's call graph, and the ones that call into my smart contract.
If I can do this, then I can feasibly reason about how my code will react to other peoples' inputs (e.g. I can prove the absence of DAO-like re-entrance bugs). The fact that Ethereum allows smart contracts to be written in undecidable languages means that this is not feasible in practice.
Because in practice, I'm trying to reason about the consequences of submitting a given transaction. A transaction can invoke many smart contracts in addition to mine. It's not enough for my code to be correct; every piece of code the transaction causes to run has to be correct as well.
If you want to know what a given transaction will do, you can simply run it locally; no need for formal analysis. Formal analysis is useful for proving properties about your program like "the total balance will always equal the sum of the accounts" and "transfers never increase the sender's balance".
But you can reason about what any possible transaction can do by reasoning about all possible inputs to your code; you don't need to know anything about how other contracts were written, since even if they are formally provable, they could send you literally any input.
Edit: Rereading your earlier comment, I understand now - you're talking about other contracts your code calls, not vice-versa. In that case, I'd point out that you're totally free to either write those contracts yourself if they're not already provably secure, or write your own code such that it's formally proved to work regardless of what those contracts do.
If I can do this, then I can feasibly reason about how my code will react to other peoples' inputs (e.g. I can prove the absence of DAO-like re-entrance bugs). The fact that Ethereum allows smart contracts to be written in undecidable languages means that this is not feasible in practice.