That's right, headings are new in XF 2.2. If you used a larger size and bold to denote headings in XF 2.1, remove formatting would work there because the font-weight and font-size are applied inline to the text.
Some of our users are surprised that "remove formatting" only removes inline formatting, especially because some copy-pasted headings just look like bold text and the user isn't aware that he actually copy-pasted a "heading". For example, the usernames that XenForo displays next to posts are H4 headings whose formatting cannot be removed with the "remove formatting" button after copy & paste. I don't use other WYSIWYG editors except for the one in XenForo and therefore cannot say whether this behavior is common but I personally would have expected this button to basically behave as if I pasted some text using Strg+Shift+V (instead of Strg+V) in the first place.
I respect your decision (of course ) but wanted to leave this feedback here nevertheless.