Crash course in video as it pertains to this topic, apologies for the general incoherent ramblings that follow but it is about all I can do to stay awake right now.
containers- various ones exist including avi, mkv, wmv, ogm, mp4 and rmvb (I shall resist the temptation to spit as I would only have to clean it up afterwards). They exist to make the life of decoders easier- AVI stands for audio video interleave and as the name implies weaves audio and video together so as to reduce the need for random access of files on a disc but it is showing how old it is with poor support of newer standards and lack of real subtitle support. MP4 is a more official container from big standards types (it is also patented rather harshly in places that consider software patents a good idea) while MKV is a somewhat more open standard with great support for just about everything so it caught the eye of most encoders fairly quickly (especially among the anime scene) however hardware support is not as great as other formats.
Note and note well that the container/extension has nothing to do with what it contains.
The act or removing a stream (audio, video, subtitles or whatever) from a container is called demuxing while the act of sticking stuff into a container is called muxing.
For MKV the tool pretty much every uses (whether they know it or not) is MKVtoolnix:
http://www.bunkus.org/videotools/mkvtoolnix/ (MKVextract is the tool to pull things out, it has a GUI called MKVextractGUI. MKVmerge makes the files and can take most forms of input).
For MP4 there are several choices but I suggest MP4box, it has a GUI in the form of YAMB:
http://yamb.unite-video.com/
For AVI it is a more general tool but avidemux is good:
http://fixounet.free.fr/avidemux/
RMVB is probably going to be a pain (there is a reason nobody likes them), they will almost certainly require encoding in a proper format.
OGM for many was the precursor to MKV and a fair bit of anime is still out there in that form.
There is nothing stopping you from demuxing from MKV and sticking it in a MP4 container, indeed unless you have extra requirements (needs to be below a given resolution or something) I suggest this over encoding again (encoding is lossy in these situations and encoding several times is never great).
MP4 is about as good as MKV when it comes to support for various formats but it falls over when it comes to subtitles. As a rule though anything beyond trimming the video or adding video onto the end will mean you need to encode it again.
standard- a way of encoding video and audio. It gets more complex very quickly but MPEG4 is a broad catch all name but includes part 10 aka H264 aka AVC, while part 2 is used in the likes of xvid and divx. H264 is more powerful (better compression for the same file size) but it comes with a resources penalty and being somewhat newer is not quite as widely supported unlike part 2.
Audio comes in several formats but the big ones are MP2, MP3 (actually part of MPEG1), ac3 (DVDs mainly but people sometimes avoid reencoding it), aac (maybe not the best audio standard but as good as it gets outside of lossless and in common use) and WMV (varying, competitive with all formats). Note that the MP4 contain can and is used for just audio (sometimes appearing with the extension m4a but that is just a rename).
subtitles: come in softsub and hardsub form. Softsub is a bundled extra file which in the case of MKV sits inside the MKV file but for most other formats it sits outside it.
Hardsub is burned into the video- if it sits in the edges you can just crop the subs out but otherwise you are not really going to be able to remove it easily (if you are especially bored you can use some of the logo removal filters)
Softsubs come in 4 main formats (there are hundreds mind)
srt- subrip text, falling out of favour but still many around. Very basic format with nothing all that special.
vobsub- the sub and idx file you might see when you get a video. While subrip is text based DVDs use pictures and as OCRing stuff into text is a pain many people just dump the subs into this format. Not that common in anime circles (even DVD rip groups) but everywhere else it is now probably the number one format.
The other two I will merge, they are SSA and ASS (substation alpha and advanced substation alpha). They use an odd XML like format but can do fun things like place themselves anywhere on screen, do karaoke subs (note that while it can and may have started as such some anime groups hardsub this into the intro and so a softsub the rest of the time), change fonts and colours and the like.
If you must convert them then three applications I use are subrip, subtitle workshop and subtitle creator (mainly for DVDs but worth having anyway).
If you are encoding you can burn subtitles in with many things but
http://forum.videohelp.com/threads/214768-...h-virtualdubmod is a good intro to it all.
As you have found out hardware decoders (especially big name ones) are usually troubled by anything slightly deviating from their known parameters (it is why stuff like an original xbox with XBMC is still worth a look in) and this can stretch to parts of the whole spec (earlier ipods (not sure about later ones) notably left out support for some of the better compression variations of AAC like HE-AAC). It is better than it was some 6 or so years ago but still far from acceptable in my opinion.
Never pay for a general encoding application (some of the more specialist stuff is a different matter) as most are based on open source stuff you can find just as easily. My choice is megui or one of the ones in
http://forum.doom9.org/forumdisplay.php?f=78 but they may not be quite as easy to handle (for what it is worth this side of good AI you will not see any "one click encoder" work as well as someone who took a few minutes to play with some settings, good applications there though will have some support for the various devices and their limits).
