I've had good experience using mkvtoolnix to mux video into an mkv with subtitles included. Not sure if mkv support is widespread, but as janky as the TV was with other formats, mkv worked great every time.
Installing MPC-HC during K-Lite Code pack as my primary media player has taken place of VLC for me this last year. I have been using VLC as music player only with some Winamp-like no-viewport UI lately.
VLC works most of the time. That said some videos VLC can't seem to decode correctly - I never get VLC complaining about unsupported file formats, but I do get weird artifacts and glitched rendering when I try to play certain ones.
It's then that I usually try MPV or MPlayer. One of those will usually play the video correctly.