Eg, if you do Haskell and just verify the function you are running is not in the IO monad, you might miss some usage of UnsafePerformIO. Even if you check their code, if you let them specify dependencies they might manages to sneak a buggy use of UnsafePerformIO into a library they submitted to hackage.
Plus, your restriction is essentially: no clock, no contact with the outside world, no threading, and a carefully considered interface to the host program to prevent time leaks.
For many usecases, this is not workable
Disallowing direct access to the outside world is a big restriction, but it may be that a lot of the things you'd want to do inside a sandboxed application that aren't safe could be delegated to trusted code through an appropriate interface.
Threading isn't necessarily a problem; the Haskell Par monad for instance should be fine as there is no program-visible way to know which of two sub-tasks executed in parallel finished first.
Presumably, this could be fixed easily by using the phantom type trick (same as ST) but it would make the type signatures ugly and possibly break existing code. (Maybe there's a more modern alternative to phantom types?) So, yeah, you might not want to use the Par monad as it's currently implemented in ghc as your secure parallel sandbox.
The online docs suggest using lvish if you want a safer Par monad interface, which I'm not familiar with (though the lvish docs say that it's not referentially transparent if you cheat and use Eq or Ord instances that lie).
The general idea seems sound, though -- it should be possible to have parallelism in a sandbox environment without allowing the sandboxed program to conditionally execute code based on which of several threads finished some task first.
Perhaps we just need to have a more restricted idea about what untrusted code is allowed to do.