AFAIK Xvid decoder is not (yet) fully optimized for speed, so we only have to wait, developers are working on other things ATM. This is because IMHO if your system can't fully reproduce all frames in a video, the output will be not good whatever is the way the decoder handles them... so i'll not call this a "bug"!
Considering The amount of encoding time it takes to make these files why not just reduce the resolution suitably to speed up encoding/decoding performance? This seems like the best solution to me.
B-frames do cost a little extra CPU-time, but in this case they would actually help: You can skip decoding of some or all B-frames if needed, without messing up any other frames. But if you're encoding only for playback on slow computers, then yes, use lower resolution and no qpel/gmc.
... or standalone software players based on linux, such as Movix or Geexbox. Just download the ISO, burn it, boot from that CD-Rom and insert the media containing the movie. *BANG* you're done :)