It handles DivX/XviD AVI very well, at resolutions up to 720x480.  I'm not sure if it can play other types of AVI (I assume it can't), because I haven't tried.  It should technically be able to play mp4, but it doesn't (although last time I checked was a couple of Firmwares ago, they might have changed something since then).  And I have no idea what mkv even is.
I just make sure I run all my videos through Pocket DivX encoder, they all run perfectly after going through that.  I actually use the highest quality Archos settings on that.  GP2X handles that without even clocking to the full 200 mhz (most of the time).
EDIT: PSyMastR beat me to it.