[gaspar0069]

...
However, the media starting from the beginning was still happening. Close to the end, you can see me changing the channels and about a third of the time, the media starts from the beginning rather than the middle. This was not happening in 0.5.8e iirc
...

I ran into this problem too and am using OpenElec 4.2.1 (Gotham) and 0.5.8g.

It may be related to this issue where Kodi is not always ready/able to seek immediately after switching to a new file: http://forum.kodi.tv/showthread.php?tid=161709

The user above found that adding a small delay to his code allowed it to work as intended.

The corresponding area in Overlay.py is around line 939 in 0.5.8g where it calls self.Player.seekTime().
I have a small solution that checks xbmc.Player().getTime() for a particular range of values prior to seeking and delays 100ms at a time until xbmc is ready (at most just 1 iteration in my testing). There is certainly a more elegant solution, but this has worked for me and may help lead to a more proper fix.

I won't post the code here publicly to save all involved any trouble, but I can PM the diff to coders that are interested.

On my own installation, it solved the issue of videos randomly starting from the beginning when changing the channel either via the EPG or Up/Down.