One way of looking at this is saying that since the state space is so large -- even if finite -- then treating it as infinite is a valid approximation. But I think that there's a better way to look at this which gives a sense of the problem. When finite domains are concerned, instead of looking at the canonical halting problem, we should consider the bounded halting problem (see, e.g., the time and space hierarchy theorems; while the space version is more suitable for your problem description, we'll look at the time version, as it's a bit simpler), sometimes also called SHORT DTM (whereas the space-restricted version is sometimes called COMPACT DTM), and ask ourselves the following question: given a TM $M$, an input $x$ and a natural number $t$, what is the worst-case complexity of telling whether $M$ halts on input $x$ in under $t$ steps? Using a diagonalization proof nearly identical to that of the original halting problem, we can see that we cannot answer the question in under $t$ states. I.e. there is no algorithm more efficient than the brute-force one you've described.
You can then ask, if we can work really hard once but then answer the question efficiently (i.e. in less than the actual running time) for all inputs for a machine $M$. More formally, we can ask whether for every machine $M$, there exists a natural constant $k$ such that given $M$ and any inputs $x_1, ..., x_k$ we can tell whether $M$ halts on each of them in under $t$ steps and do so efficiently, i.e. in under $k \cdot t$ steps? The answer to that is, similarly, no. Proof: take the universal TM as $M$ and see that if we could answer the question efficiently we'd get a contradiction with bounded halting.
Interestingly, these two proofs don't require true diagonalization, i.e. they don't require that we can really simulate the UTM, only that we're able to simulate it for up to $t$ steps, so this result is rigorous even for so called "total functional" languages, that can't interpret themselves. A little more thought would show what this result truly means: we cannot answer any question (a la Rice's theorem) about a TM (even a total one) in less time the the number of states it has (or the number of states we're interested in). We can say that the complexity for answering a non-trivial question about a TM (even a total one) is $\Omega(|S|)$, where $S$ is the set of states. This result happens to be so rigorous that it applies to virtually all computation models, even DFAs (with some exceptions, I think, for PDA). For an overview of results in the finite-state case, see this survey paper by Schnoebelen.