Em nome do Ciberdúvidas, agradeço as suas observações sobre a formação dos gentílicos que refere. A resposta em causa vai ser reformulada.
Sobre os nomes de países (corónimos discutidos na pergunta e respectivos gentílicos):
Bucovina (ou Bucóvina, conforme indicado no Vocabulário da Língua Portuguesa, de Rebelo Gonçalves): tem razão o consulente em relação aos gentílicos, que deverão ser bucoviniano ou bucovino.
Olténia, Ruténia, Munténia:com a excepção de Ruténia, que tem o gentílico ruteno (forma registada por R. Gonçalves, op. cit.), não há gentílico registado em dicionário nem forma consagrada, pelo que as formas constituídas pelos radicais de Olténia e Munténia — olten-, munten- — podem ter associadas as terminações -io ou -iano ou até simplesmente verem acrescentado o índice temático -o (ou -a para o feminino), de forma a criar olteno e munteno.
Dobruja (e não "Dobrogea", forma romena): é a forma portuguesa, registada em enciclopédias publicadas no séc. XX em Portugal (Grande Enciclopédia Portuguesa e Brasileira e Enciclopédia Verbo Luso-Brasileira de Cultura); não existe forma gentílica tradicional nem dicionarizada, pelo que são possíveis dobrujano, dobrujês, dobrujense.
Banato (melhor que Banat; ver José Pedro Machado, Dicionário Onomástico etimológico da Língua Portuguesa, Lisboa, Livros Horizonte): não há forma gentílica consagrada, pelo que se aceitam as formas banatano, banatiano, banatense ou banatês, que estão bem formadas.
Bessarábia: tem efectivamente por gentílico a forma bessarábio (Dicionário Houaiss).
Valáquia: valáquio como forma de adjectivo e substantivo (Valáquios, com maiúscula, é usado como etnónimo, isto é, ou seja, como designação genérica dos naturais ou habitantes da região; Gonçalves, op. cit.); como forma de designar o dialecto da Valáquia, recomendou-se valáquico (idem), mas actualmente regista-se só valáquio para esse caso.
Moldávia: tem moldávio como forma de adjectivo e substantivo (Moldávios, com maiúscula, é usado como etnónimo, isto é, como designação genérica dos naturais ou habitantes da região; Gonçalves op.cit); como forma de designar o dialecto da Moldávia, procurou impor-se moldávico (idem), mas actualmente regista-se só moldavo para esse caso.
Transilvânia: tem como forma de adjectivo e substantivo transilvano (pode também ser usada para designar dialectos da região) e Transilvanos como etnónimo.
Crișana e Maramureș: não há nem aportuguesamento nem gentílico consagrados; se houver necessidade de referir os naturais ou habitantes dessas regiões, usa-se uma perífrase («os naturais, os habitantes, a população de Crișana e Maramureș) ou terão de ser criados gentílicos seguindo os modelos e os critérios mencionados na questão.
