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.