Due to the open and wild out of control video encoders out there, you can't count of Plex to play say as many files as VLC Player.

There appears to be no cure but to learn about video encoding and transcoding. I use Handbrake a lot.