Thanks all for your answers. Looks like newer versions of Chrome fix the problem.
I wrongly assumed that if a codec is supported by the browser, it will automatically be supported by MSE. In practice, that's not the case. A browser can support a set of video codecs (h264/webM/theora/...), it can also support MSE, but just a subset of video codecs when "injecting" the video into MSE buffers.
The compatibility matrix between MSE and codecs doesn't only depends on the browser but also on the OS. So for example, Google Chrome Supports MSE+h264 on Windows and Android but not (yet?) on Linux. VP9+MSE is supported on Windows and Linux but not on Android.
Youtube has a very useful test page to check browser support for MSE & h264/VP9 codecs: