Ok so for those interested I have found a workaround that is 100% working.
People mentioned it above but for the record, I simply converted my H.264 mp4 videos to VP9 using ffmpeg. It is crucial to keep the videos in mp4.
It is 100% working on Steam Deck and videos play fine, without using Proton GE or any other tools.