I have had success with "XVID" in both code and description. Anything with "DX50" has given me problems (axxo?).
The other thing is that the DSM-510 seems touchy with the MIME type. What media server are you using? I use mediatomb off of a NAS, too. The settings for the DSM-510 are well documented right in the config file, and are different from other DSMs.
If you happen to have a "distribution" running on your NAS (Debian?), there is the "cfourcc" package with the fourCC utility compiled to run right on the NAS. Might it is available on ipkg, too. Same for mediatomb.
Next, if your avi's play very jerky (only seem to refresh the screen at major scene changes), chances are the file was encoded with Global Motion Compensation (GMC). This player wants nothing to do with it. Same with Quarter Pixel (QPEL). It is supposed to be part of the MPEG 4 ASP (ADVANCED simple profile) spec, but no standalone that I know of plays them)
I would do the fourCC thing first, then go from there. Chances are changing both to "XVID" (uppercase, no quotes) will work. Best of luck. Keep us posted.