A forma deocolônia está consignada no Dicionário Unesp do Português Contemporâneo. Sendo o elemento deo- uma truncação do inglês deodorant ou do francês déodorant, pode-se também criar "deso-", extraído de desodorante, que no Brasil é o mesmo que desodorizante em Portugal. Deste modo, a forma proposta na pergunta é possível, mas falta-lhe o mais importante em qualquer língua: o uso. Talvez o consulente consiga ganhar adeptos para este neologismo.
O mesmo se diga acerca de "desodorante-colônia" ou "colônia-desodorante", no Brasil, ou "desodorizante-colónia" ou "colónia-desodorizante". E dado que se trata de um nome formado por dois nomes justapostos, é de facto recomendável o uso do hífen.