As long as it's a coastal region, I don't see the problem.
If it's landlocked, and still allowed to build a shipyard, that's a bug.
So am I misreading the meaning of navies as groups of military-class vessels? How would you get the infrastructure to build those in a woodland region? Or a stronghold that can't even muster up enough competence to change bonds into gold?
From a gameplay perspective I see no issue (maybe even the need to allow for all sea zones to have navies, even if no cities are on its coasts)