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

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.