La VM Dalvik ejecuta los archivos *.dex correspondientes a una aplicación cuando se ejecuta dicha aplicación. Un archivo *.odex es la versión optimizada de un archivo *.dex que se ha creado específicamente para un dispositivo o plataforma concreta. La ventaja de crear un archivo *.odex es que la aplicación se ejecuta mucho más rápido ya que la optimización que la VM tiene que realizar en el arranque de la app ya está realizada de antemano.
Los OEMs como Samsung que lanzan ROMs para sus dispositivos suelen odexar todos los paquetes de aplicaciones para aprovechar el arranque más rápido de la app. Como resultado, se dice que las ROMs de stock están "odexadas".
La desventaja de una ROM odexada es que es imposible tematizarla o modificarla y también es imposible adaptarla para su uso en cualquier dispositivo/plataforma que no sea aquella para la que fue específicamente odexada. Como resultado, la mayoría de los desarrolladores de ROMs personalizadas optan por liberar sus ROMs sin odexar los paquetes de aplicaciones.
Una ROM "deodexada" técnicamente significa que fue originalmente odexada y alguien se tomó el esfuerzo de deodexarla explícitamente - normalmente utilizando una utilidad de deodexación. Sin embargo, también ha llegado a significar cualquier ROM que no tenía los paquetes de aplicaciones odexados en primer lugar.
Espero que eso ayude.