Video encoding is not embarrassingly parallel; no kind of compression ever can be, because if any bit doesn't depend on the previous bit you've wasted it. It is pretty suited to ASICs.
Codecs are only efficient up to a certain image size, and then stop working because all the details are too large-scale for them. HEVC works much better than H.264 on 4K. Besides that, there's higher bit depth pixels, 3D, that kind of stuff.
Also there's usually so many mistakes and compromises in any standard that you can always find something to fix in the next one.
"Video encoding is not embarrassingly parallel; no kind of compression ever can be, because if any bit doesn't depend on the previous bit you've wasted it."
That objection makes no sense. That just implies that at worse parallelization may cost some encoding efficiency. In general, we are quite often willing to pay for that encoding efficiency with gusto given the speedup we can obtain. For instance, http://compression.ca/pbzip2/.
I don't think you two are using the same definition of embarrassingly parallel (emphasis mine). Given real world constraints, video compression is nowhere near as embarrassingly parallel as, say, motion jpeg. Many of the recent improvements (eg. better motion vector estimation) only see any benefit when you're encoding sequentially.
If you have that much need for a speedup, you probably have multiple video streams going (like you're Youtube or a livestream broadcaster). In that case, it's better to do one video per CPU, and now you really are parallel.
Also, you can get up to 4x parallel through slice-threads safely on one video, or 16x through x264's frame-threads if you don't care about your target bitrate. I wouldn't consider that embarrassingly parallel until it's up to 1024x or so, but maybe you do.
Are there not stages of compression that are highly parallelizable, though? Like basic transformations that operate locally on the image (maybe DCT, per-block motion vector calculation)?
But that doesn't happen - when you're encoding, the DCT isn't actually run on the image but on the output of previous compression steps (prediction) which are based on the last encoded block. So there's a dependency on every pixel of the image to the upper left of you.
And when you're decoding, it just never ends up worth it to read the whole bitstream so you have a whole frame of motion vectors to do it at once. The whole data locality thing.
Codecs are only efficient up to a certain image size, and then stop working because all the details are too large-scale for them. HEVC works much better than H.264 on 4K. Besides that, there's higher bit depth pixels, 3D, that kind of stuff.
Also there's usually so many mistakes and compromises in any standard that you can always find something to fix in the next one.