Isn't video transcoding easily parallelizable? I mean just split the video into N equal parts (at keyframes) and divide the work.
And as for seams: https://en.wikipedia.org/wiki/Deblocking_filter
As such, they are suboptimal by default if a lot of motion occurs.
What H.264 encoder are you using that does not have a scene change detection option?