HM Fly would be unbalanced if a players obtains the move and travel all over the regions with ease. What if we add some restrictions for it to be balanced. Here's some ideas I thought of.
Since currently the game has two regions Kanto and Johto. If we can add "Multi" versions of Fly to make it balanced. For example HM Fly Kanto and HM Fly Johto tagged on the side of the move, so that players won't be confused, and same for the upcoming Hoenn HM Fly as well.
The requirements to use.
Players must complete the NPC quest for Fly first. Which I assume there is one in the game.
Players must beat the gym leaders in the town or beating Elite Four of the that region.
Pokemons with different versions HM Fly on their moveset won't work, only one at it time.
Pokemons from the same region may use that versions of Fly.
Maybe add some cooldown timer or a limit per day, so players won't able use it all time, so that the bikes/mounts won't be useless. During the cooldown they also use the subway as well. There's players everywhere that haven't beaten the gyms leader or Elite Four or simply don't have enough pokedollars, they can use this method for a bit until they beat it.
As for pokemons who learns fly by level up. Depending on the region they are caught, they learn that region of fly. For example, I caught a salemance in Johto, so it learns HM Fly johto.
I hope this is undersandable, english isn't my language.