I just ran into the same issue and realized that I only encounter the issue when I deploy the build to the steam deck using the SteamOS Devkit Client!
If the exact same build is uploaded to the steam server and then downloaded to the steam deck (basically the standard way to deploy to regular steam users), my h264 encoded mp4 video plays perfectly fine on the steam deck.