Your questions address a feature that many of us want Apple to support...the ability to recover and/or redistribute VPP codes, which is so important especially in schools. However, the process you are asking for is currently unsupported by Apple and most MDM providers. Currently the only way to recover VPP codes is to remove the app from Supervised iPad(s) using Apple Configurator. If you don't have the iPad, you can't recover the VPP code(s). So yes (unfortunately) if the iOS devices is lost/stolen/broken then the VPP redemption codes are lost.
If you were in a situation where a large number of devices were stolen all at once (like a whole cart or multiple carts), you may be able to call Apple Store support for Education at 1-800-800-2775 and explain the situation. I have heard of circumstances where VPP codes have been returned/recovered but that is a rare circumstance.
I know its not the answer you wanted to hear, but I hope this answers your question.