Não precisaria necessariamente de uma gráfica, que geralmente só pegam serviços grandes (acima de 1000 copias), qualquer lugar que trabalhe com impressões pode fazer isso pra você, algumas podem até pesquisar o arquivo.
Eu trabalho com impressões e só forneço papel sulfite normal ou fotográfico, mas fazemos em outros tipos de papel se o cliente trouxer ou encomendar previamente, só que no meu caso não fazemos pesquisa, a pessoa nos envia o PDF para impressão.
Acredito que qualquer cidade tenha pelo menos 1 estabelecimento que faça isso, aqui onde moro é uma cidade pequena de 15.000 habitantes e tem uns 4 locais assim e 1 gráfica.
Agora se for uma impressão mais especifica, tipo um tile ou mapa de campanha já é mais difícil de achar. Uma dica de solução neste caso seria fazer uma impressão em papel adesivo e colar em um pedaço de papel panama.