Reject messages were never a 'stable interface' and couldn't really be-- the issue is that which reason for rejecting you provide depends critically on the exact construction of the software. So random, seemingly unrelated changes could stir them around.
Say, for example that you send a transaction that was already confirmed a few blocks ago. Is that a inputs-already-spent rejection, or is that an inputs-don't-exist rejection? The former is only even possible to return if you have a pretty expensive index of every confirmed transaction-- something that isn't required for consensus operation but which Bitcoin originally had.
Essentially rejections make for a bad interface because they inherently expose otherwise irrelevant internals. They also result in privacy leaks, dos attacks, etc... and searching showed zero (I believe absolutely zero, but it might have been just nearly zero) usage outside of test harnesses / debugging output.
The protocol didn't need to be bumped because there never was any guarantee that reject messages would be generated, and unknown messages are just ignored in the protocol. I'm pretty sure the protocol version wasn't bumped for their introduction either-- at least a bump is not mentioned in the BIP.
Good protocol design:
1. Be strict in what you accept. Otherwise it becomes impossible to change anything without accidentally breaking compatibility with broken inputs.
2. Liberal in the kinds of things you send, within the strict allowance of the spec so that all corner cases get tested.
3. Silence is golden. Information you don't send usually can't cause interop problems or compromise the user's privacy.