I don't feel pre-pending 'New' to a name is good.
The Arduino team didn't do that. A member of the forum saw a need for a better software serial class, and developed a new one. What to call it? Well, SoftwareSerial2 seems kind of clunky.
The library was posted on the forum and playground, got good reviews, and was acknowledged to be better than SoftwareSerial. So, support for SoftwareSerial was dropped. It has not been the preferred software serial class for many versions of the IDE.
I don't think failing to include library example code, which clearly exist, in the download is a good approach to clearly announcing that a library is deprecated. That feels wrong.
How would you do it? Keep in mind that paperwork and documentation always tends to take a back seat to new development. I know. I've been a developer for 30+ years, and I don't do documentation unless I'm bored out of my skull. There is always something new to work on, learn, or explore.