Uma construção alternativa é recorrer à preposição com (ver Francisco Fernandes, Dicionário de Regimes de Substantivos e Adjetivos, São Paulo, Globo, 1995), mas com algumas modificações:

«A escola tem parceria com outras instituições.»
«Deve promover-se a parceria da escola com outras instituições.»

Considero, no entanto, que a preposição entre pode ser usada com parceria, apesar de pleonástica (uma parceria já  pressupõe uma relação entre duas partes):

«É preciso promover a parceria entre a escola e outras instituições.»

Há mais casos de uso pleonástico de preposições com verbos; por exemplo, «entrar em» é redundante porque entrar já inclui a noção de movimento para o interior de algo, que está contida na preposição em. Nestes casos, não vale a pena procurar formas mais ou menos rebuscadas de evitar a redundância, porque tais preposições estão consagradas pelo uso e seria pouco natural substituí-las por outras construções.

Quanto à alternativa que envolve firmar, devo dizer que ela nada altera: a preposição continua a ser governada por parceria, porque firmada é apenas um particípio adjectival que modifica aquele substantivo.