What is the difference between odexed and deodexed ROMs? What is the difference between odexed and deodexed ROMs? Which is the standard (stock) ROMs that ship use?
A .dex file is basically a compiled bytecode version of an app that has been built for the Dalvik VM which Android's apps run on. I believe it is short for Dalvik Executable, but I'm not sure if I'm remembering that correctly.

An .odex file is an Optimized .dex file (hence the 'o'), meaning that it has basically been pre-compiled for a specific platform. The advantage to this is that startup time is much faster since the VM doesn't have to perform any optimizing at startup/runtime. The disadvantages are 1) That it takes up some extra space and 2) An odexed app won't run properly if it's put onto another device, and it must have the associated .odex file to run at all.

ROMs are typically released in deodexed form because they can be themed and modified fairly easily, whereas theming/modifying an odexed ROM is basically impossible (at best things would crash like crazy). Some people also choose to release their ROMs in odexed versions for people who would prefer the performance gains.

Most of the stock ROMs I've seen are odexed, I assume because the carriers/manufacturers want the performance boost. They also don't have any kind of official theming methods, so they probably don't care if you can't change the colors of your status icons or your system text or whatnot. Plus they have the advantage of knowing what device they want their system to run on, so they can pre-compile the .odex files very easily, I imagine. As an added bonus, it makes it difficult to pull .apk files off of the device and share them with people.

Edit: Since I just realized that I was not very explicit about the difference here - an "odexed" ROM is one where the apps have been precompiled, and thus contain associated .odex files which are external to the .apk files. A "deodexed" ROM is one where data that would be optimized in the .odex files has been more or less merged back into the .apk files (meaning it is not optimized but basically platform agnostic), thus the .apk files are self-contained and there are no .odex files. This is usually just done with a deodexing utility, such as smali/baksmali.