I think that would have it's own complexities. You'd have to ship each phone with a compiler and related toolchain. You'd also end up with two copies of each

I think that would have it's own complexities. You'd have to ship each phone with a compiler and related toolchain. You'd also end up with two copies of each application installed on the users phone (one in the neutral format and one native). Sound like kind of a messy approach. Really, the existing non-jit'ed Dalvik VM runs fast enough. If you think about it, their decision to ship a non-JIT VM and enhance the platform with JIT later is very much like Apple's approach with the iPhone of initially shipping the product without cut-and-paste and without any native API for third party apps, but then enhancing the platform later by adding those (and many other) features later. Both companies shipped when they had a platform that was "good enough", then have kept iterating and improving.