One possible example is a Pokémon that didn’t learn the move through the actual HM but through other means. If you got to a location using that HM move, deleted it and didn’t actually have the HM to add it back, you’d be stuck without Fly. Plenty of HMs like Waterfall, Dive and others are level-up moves.
It would also be weird if you were able to delete Surf in the middle of use.