AviSub will internalize a separate subtitle file, but the 360 will not read from the internal sub. It only takes a few seconds/minutes because it doesn't do any actual re-encoding, its just a file merging process.
The only way to get subtitles with DivX to be displayed on the 360, is to hard code the subs. The requires a complete re-encoding of the video. AviRecomp works great and is very simple to use, but as you mentioned, takes much longer.
There may be support for one of the on-the-fly transcoders, but as far as from a disc or usb hdd, it must be a hardsub.
This has been discussed in this thread --->
http://forums.xbox-s...howtopic=640095and also in the pinned FAQ --->
http://forums.xbox-s...howtopic=637843