Part of the issue is that even with pretty fine-grained symbolic execution there are simple programming patterns which can induce the entire memory space, or a very large portion of it, as a possible jump target.
Are those patterns likely to be used, though? If one is detected, could the tool we're hypothesizing about inform a human who'd be able to understand what was going on?
I'm always confused between symbolic evaluation and abstract interpretation but, according to Wikipedia, abstract interpretation is the more general term. I'd love to have the time and the ability to work on this kind of thing, up to and including partial evaluation. Really a lot of potential in this area, I think.
If you're really interested, the decompiler I built as part of this project performs a symbolic execution of programs for a very simple architecture and (conservatively) tracks the values which could reach registers at a given point in the program:
I call the technique "register smearing" and it's only remotely feasible because Chip8 has lots of registers (if an accumulator was constantly being clobbered you wouldn't get much useful information) and programs are exceedingly small (<3.5kb).
As you'd expect, for simple programs this works great and has even helped find bugs in some of the example Chip8 ROMs in the wild. However, it rapidly breaks down when you start working with memory-intensive programs or anything involving self-modifying code. There's still room for improvement, but at the end of the day you can't solve the halting problem and there is a diminishing return on greater complexity in your decompiler.
Why? This sounds like symbolic evaluation. You certainly can't know in all cases. But at worst, you can come up with the set of possible jump targets.