Couple of things.

More than likely, if you want to pay less that a grand for a device, you may have to re encode. Why you say you "certainly" wouldn't do so doesn't make a lot of sense to me. Find an encoder with drop folders and come back in a few days. (I do encoding for a living for ABC News, so I love any chance to encode, finding the smallest file size with the highest quality - of course with the 18 encoding nodes we have between our two farms, I could likely do your entire collection in the format of your choice in an hour or so, so perhaps I am not feeling your pain).

Why don't you post a link to one of your shorter videos and one of us can download it and test it for you to let you know about playback across a number of the media players? I can also take your existing xvid and convert it into a couple of test encodes using lower bitrates. At the very least, it will identify if you can transcode instead of re encode. Depends on how many B frames per I frame. MPEGs are always the worst to transcode, in my experience.