Remuxing would be good. I have files that I can play on the Sony TVs here via USB, but I haven't been able to figure out a way to get them playing on them via DLNA without transcoding.
I can handle transcoding to DVD-quality (which is what MC uses by default) but not HD
I also have to change the mimetype/video DLNA override codes manually depending on the framerate and format of the file. (DVD, HD MPEG2, MPEG4)
Similarly, my TVs won't play back MKV, but supports both 1080p MPEG2 and H.264 video decoding. (no VC-1 though)
It's not really been an issue for me before since I just watch content on my main TV which is connected to the HTPC via HDMI, but it never really occurred to me to try setting up DLNA streaming to the others until using Media Center. It would be pretty nice if I could be watching a film on the main TV and someone else had access to other films/TV shows at the same time.