Over on Full Moon Blog, Saif is having trouble finding a cheap DVD player that can handle VCDs. When I was researching DVD players for Christmas 2002, I found a website called dvdrhelp.com, with reviews of hundreds of DVD players, searchable by compatibility with different formats. Compatibility lists are based on actual user experience. There are also reviews, so you can learn crucial details -- for example, the color of the serial number sticker on one model is a clue to whether the unit will support MPEG-1 video.
We have a cheapo APEX which will display family photos (JPGs) off of home-burned CD-Rs with no problem.
The impression I have is that the more expensive the unit, the fewer formats it supports. The basic decoding technology will handle just about anything, but it costs the manufacturer to build in the technology to filter out anything that isn't a real commercial DVD.