MPEG -4 isn't really a type of video it is more a category of encoding methods. Xvid, Divx, H.264 are all mp4 files. You can even take a xvid file and change the header information to h.264 and h.264 decoders will play the file. They mainly vary in what frame information they use to encode. H.264 has smaller file sizes because the encoding allows a frame to be built from frames both before and after the current frame, which is also why it is a terrible format to edit, none of the individual frames contain the complete frame data.
MKV is really not a good container. The reason is that it is far too flexible on what it allows and that is why you get so many incompatibilities between players. It is like a wildcard type of container where almost anything goes so not every player can accommodate all those differences. A player that says it has MKV support really means nothing but that it can open the file, it says nothing about its ability to play the content.
MP4 is the container I would use for all new content. It is standardized and fairly strict on what it allows inside it. While that makes it not as flexible as MKV , it is better in the long run because the mix of codecs and formats has done nothing but complicate distributing video on the internet. MP4 is supported by all the new and upcoming media players and they are dropping support for everything else. Codecs to use should be based on h.264 because that too will be the main codec and h.264 can decode xvid with the right software installed.