That patch fixes Ed's test case. It makes the assumption that when moving content around like this, all that matters is the comparable annotation objects, and discards the ones on the pasted content which are comparable-to the surrounding annotations that are going to get applied.
I chose the order of application that'll get us <p><b id="b">Baro</b></p>, but it'd be easy to adjust it so we get <p><b id="b">Bar</b><b id="a">o</b></p> instead. It's just a matter of which annotation set gets priority.
If the approach seems good, I can add it for external pastes as well.