It was not that long ago that 25 kHz FM was Narrow band. Does that make 12.5 kHz FM Ultra Narrow? What will 6.25 kHz FM be called Super Narrow?
Just how narrow can FM go and still possess decent audio quality?
When you do not have sufficient FM deviation to convey human speech.
For example, telco grade circuits are rated from 300-3000 Hz. There is significant roll off of performance above 3000 Hz for speech. The range of 300-3000 is more than adequate to convey a human voice. Think of how we are limited on SSB to around 2.7 KHz (well, most nice hams do).
If we had to, we should be just fine on a 6.25 KHz channel spacing with only some minor loss of high frequency response.
Running on narrower channel spacing with less FM deviation would require that we have better frequency stability and more precise oscillators so everyone stays on the center frequency. Also the linearity of the signal is important and proper pre-de emphasis.
You do not need to be in a digital mode for this to work. Digital CODEC's take an analog speech signal and run it through a D/A converter, run compression on the digital stream and zap the digital stream across the air with a more advanced modulation technique.
There is a great deal of hype about how "different" narrowbanding will be for public safety agencies. Lots of manufacturers are using this to push the $5000 HT that is capable of all sorts of digital modes, trunking and encryption. One municipality I was consulting for was concerned about replacing >300 alert receivers in the local schools because the Bat-Wing people said "they would not support narrowband analog". I talked myself blue in the face that they did not need to spend a quarter million dollars in replacing those receivers but the manufacturer would not relent and did the full court press because they are in the business of selling equipment, not common sense.
The VHF FM receiver that was set up for 25 KHz channels will work just fine when receiving a transmitter that is putting out 12.5 KHz deviation. The only thing they will notice is that the recovered audio is quieter. The solution, turn up the volume control. If you want to sell them something then make it radio service to go through and peak the receivers for optimal performance from a 12.5 KHz signal.
Back in 1980 we were aligning telemetry radios to operate with 1.5 KHz deviation on VHF splinter (6.25 KHz spacing), 2.5 KHz deviation on UHF. It was simple FSK modem operation at 600 baud but it worked just fine.
Do this test at home (or on your computer). Listen to a voice broadcast like the news from an FM station. Use the equalizer and chop off everything above 3000 Hz. It will not sound musical but the speech is perfectly intelligible.