Depois de algum tempo, conseguimos usar Comodo e Geotrust --quick & certificados baratos. É assim:
1) Comodo parece pedir contas de e-mail *@city.gov em seu método de verificação de domínio comum. No entanto, usando seus métodos alternativos, você pode verificar seu subdomínio adicionando um arquivo de texto, como: link
O truque é que o HASHFILE.txt contém outro hash, ele não funciona se o HASHFILE.txt estiver vazio - o que é diferente das verificações do Google -. (esse foi meu erro)
2) Certificados GeoTrust (como o RapidSSL) podem ser validados usando endereços de email de diferentes níveis. Isto é: você pode verificar seu subdomínio se puder receber e-mails em: *@department.area.city.gov.
Nós fomos com o Comodo, mas o Geotrust deveria funcionar também.
Obrigado pela sua ajuda.