It is definitely impossible to efficiently compile code with evals for all possible programs, but lots of code using the data-as-code paradigm generates data that is completely independent of input sources (macro like). This could be computed at compile time and thus efficiently compiled. A similar technique has been used for making Haskell run faster, called super compilation, and it shouldn't be too hard to implement in any functional language.
For evals that can't be compiled, well, it would be nice to still be able to do the dynamic inefficient eval, without botching the efficiency of the entire program. Do the normal dead code analysis, the eval might not work right, so provide a warning. The programmer can always do things to ensure any code they need isn't dead code eliminated by using it elsewhere. Yeah this is messy, but it leaves the choice up to the programmer and has no less power.