Корректно со строчной: московский губернатор, тюменский главный врач. 

В орфографическом словаре – тоже с прописной: север, -а и (полярные и приполярные территории, Арктика) Север, -а; Крайний Север; Европейский Север, Кольский Север, Обский Север, Тюменский Север; Война Севера и Юга (в США, ист.).

Вот что написано о прилагательных с суфиксом -ск- в полном академическом справочнике «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина:

«В большинстве прилагательных с суффиксом -ск- согласный л перед суффиксом мягкий, поэтому после л пишется ь, например: сельский, уральский, барнаульский. Однако в некоторых прилагательных, образованных от нерусских собственных географических названий, сохраняется твердый л, поэтому ь не пишется, например: кызылский, ямалский (наряду с вариантами кызыльский, ямальский)».

«В большинстве прилагательных с суффиксом -ск- согласные н и р перед суффиксом – твердые, поэтому ь в них не пишется: конский, казанский, тюменский, рыцарский, январский, егерский. Однако в следующих прилагательных эти согласные перед суффиксом -ск- мягкие, в них после н и р пишется ь: день-деньской, июньский, сентябрьский, октябрьский, ноябрьский, декабрьский, а также во многих прилагательных, образованных от нерусских собственных географических названий на -нь, например: тянь-шаньский, тайваньский, пномпеньский, торуньский, сычуаньский, тяньцзиньский».

Что касается слов пермский и кемский, то мягкий знак в них не пишется по простой причине: согласный м произносится перед суффиксом -ск- твердо.