Are ROMs with deodexed programs faster or slower than odexed?
Deodexed ROMs do not have the .odex files integrated into the .apk's, they are removed.  What eldareathis meant in his answer to the other question is that the reliance of the .apk's on the .odex files is removed; some information is integrated back into the .apk, but not the actual .odex file itself.  This page has some technical details.

Deodexed ROMs may be slightly slower because of this; however I believe that as the Dalvik cache is built up from using the ROM, the performance gap is minimized.