Yeah - seems like it would be one of those things that you could allow the user to configure and they'd set it once and never again. I suppose you could switch your client to plaintext composition, but would be nice if there was a setting like you describe "don't change formatting after pasting" and/or "always strip formatting when pasting".
But keep almost all formatting (except font size) if pasted into a new empty paragraph.
But under no circumstances have the formatting under the cursor after the operation changed.
I know that breaks all convention and would probably cause more problems, but boy would I be happy.