When was not being able to release Pokemon with HM moves implemented?
This feature was implemented in Gen 3 (NOT Gen 2). In fact, you can find videos online of people getting stuck in Cianwood by releasing all their Surf-capable pokemon, much like Cinnabar in gen 1. I have also personally tested this on a real Game Boy.
Note that due to an oversight, it is possible to get stuck in D/P/Pt by trading away your Finneon to Meister if it's your only pokemon that knows Surf. You still can't release them though.