The most novel thing I've heard about Dalvik is their zygote technique for minimizing app startup time. The zygote is is a Dalvik process that's loaded and ready but for the actual bytecode it will need to run. To start a process it first makes a fork of the zygote, which allows for more shared memory and a more expensive initial setup time for the zygote without any penalty when creating new Dalvik processes.
I dunno if this technique necessitated writing their own VM however.
Most of these high-profile phones do not have Java out of the box, and getting a Java runtime can even be challenging. For example, there is no JavaVM out of the box on iPhone, Android G2/HTC-Magic, and Treo 750 WinMobile (I could not find one on my old Treo 750 WinMobile). And for the rest—well, the J2ME market is very fragmented.
Loopt seems to get it done in J2ME quite well. I don't buy it.
