Yeah - as evidenced by the NES story the other day, the elegance of AOT blows up completely as soon as there's any form of self-modifying code or even memory arithmetic tricks or jump tables. It's all possible to work around, but JIT is cleaner and more flexible in the long run.
In other words, you create a JIT to run the executable, building a profile of the execution paths at runtime, and use that profile to guide a static decompilation process. That way it should be easier to identify the sections of self-modifying code, as well as model the behaviour of this code.
The only difficulty I can see is how much time it might take to map out all the code paths, but in principal it's possible, and there may be some efficient approaches for doing so.
