Even more interesting, I did a new Ubuntu installation and I had libffmpeg.so on hand so I thought that I should copy it for now to get H.264 working faster but it turns out opera does provide it, but in wrong folder...
Easy way to get H.264 working for me was:
cd /usr/lib/x86_64-linux-gnu/opera
sudo cp -r lib lib_extra