CXBX does convert XBox executables to Windows executables, it's a form of virtualization. It patches XDK function calls to native handlers before executing the code; the rest of it stays in place. It works for the same reasons VMWare works, that the games are ran as relatively abstract user code, and they also use a pretty standard Windows interface that was easy to convert to native Windows calls. Whether or not this can be considered emulation is debateable.
From what I understand, one of the reasons the emulator never got off the ground is because the XDK versions used by games differed, and each one (even with only small differences) had to be handled explicitely.
Having said that it doesn't mean the approach doesn't work. Xeon came out of nowhere and emulated Halo (although I don't know how well). It might just be a really tedious task.
blueshogun96; I honestly wouldn't worry about cycle timings for a machine like XBox - your approach is more or less fine, although it might be better to make each instruction take half a cycle or so. The reason I say this is because on a platform like XBox it'll probably use a system call to wait for VBlank (and if you emulate those at a low level, it'll probably use the hlt instruction), at which point you can stop counting cycles and jump straight to the next interrupt. What you want to do is make sure that you can run at least as many instructions as a real XBox can. Basically it's like overclocking it some amount, which should work out okay so long as the timers and what have you are correct relative to each other.
I don't emulate cycles accurately at all for my GBA emulator, although I've improved it some over releases. As far as compatability goes, it only makes a difference for a small percentage of games, and GBA is probably more low level than XBox.
Actually getting cycle accurate emulation on XBox would be almost impossible because you'd have to account for both levels of the cache, branch mispredictions, superscalar efficiency, decoding bottlenecks.. the Pentium 3 is far from a simple chip to simulate deterministically. I'd say you really have no way of coming even close to it, even if you were willing to pay the outrageous amount of overhead necessary it'd just be too difficult.
Fortunately, what it comes down to is that the harder it is to emulate timing accurately, the harder it is for a game to have depended on timing being a certain way in the first place. The only problem is when you have buggy games that just happen to work because of parameters of the system and are thus sensitive to the timing not being too far off. Again, this is less likely on XBox than it is on other platforms because the code would in general be higher level and the environment is more abstract (protected address spaces and all let you get away with far less real bugs, not to mention that a lot of those games were probably developed on Windows anyway).