No reconoce vivienda habitual

Por ser militar me destinaron a madrid forzoso, supongo que como era mi obligación debía empadronarme en la ciudad ya que pasaría gran parte del año en Madrid, viviendo en una residencia militar, ya que mi  vivienda y única estaba en cadiz, en ese tiempo la vendí y ahora hacienda me dice que no era mi vivienda habitual, a pesar de enviarles los recibos de luz, comunidad, Internet, gas, comunidad.
Creo que lo correcto era empadronarme en Madrid donde pasaría gran parte del año, pero en ningún momento tuve otra vivienda, me empadrone en una residencia militar.

Depende de que tuvieras o no obligación de residir en esa residencia militar.
Si estabas obligado a residir en ella, es de aplicación este artículo del Reglamento. Pero si no tenías obligación de residir en ella (aunque tuvieras que residir en Madrid), no puedes aplicarlo:
 Art. 41 bis-2

No obstante, se entenderá que la vivienda no pierde el carácter de habitual cuando se produzcan las siguientes circunstancias:
Cuando se produzca el fallecimiento del contribuyente o concurran otras circunstancias que necesariamente impidan la ocupación de la vivienda, en los términos previstos en el apartado 1 de este artículo.
Cuando éste disfrute de vivienda habitual por razón de cargo o empleo y la vivienda adquirida no sea objeto de utilización, en cuyo caso el plazo antes indicado comenzará a contarse a partir de la fecha del cese.

Entiendo que te están haciendo un procedimiento de comprobación limitada del ejercicio de la venta para comprobar el derecho a la exención por reinversión en vivienda habitual, ¿No? ¿En qué momento del procedimiento estás? ¿En alegaciones?
Hay varios puntos aquí que comprobar.
En primer lugar, las viviendas habituales de militares y guardias civiles conservan ese carácter si obtienen el disfrute de vivienda por razón de cargo o empleo y la vivienda habitual no se alquila.
Es decir: no basta con que te hayan dado destino fuera de tu provincia; el destino debe conllevar el derecho de disfrute de pabellón militar.
En segundo lugar, como he dicho, la casa de Cádiz no podía alquilarse ni utilizarse de ninguna manera (ni dejársela en precario a tu hermano, por ejemplo), sino estar a tu disposición.
En tercer lugar, para tener derecho a la exención, esa casa de Cádiz tenía que haber alcanzado el "estatus" de vivienda habitual: tenías que haberla habitado en 12 meses desde su compra y haber residido en ella 3 años o, al menos, hasta que te mandaran a Madrid. Es decir: no vale comprarla "con intención de habitarla al finalizar el cargo de Madrid" y venderla antes de que eso ocurra.

Si cumples todos los requisitos (la vivienda de Cádiz llegó a adquirir la consideración de vivienda habitual antes de irte a Madrid, quedó desocupada y a tu disposición mientras estuviste allí y, el destino de Madrid, conllevaba el disfrute de una vivienda por razón de cargo y empleo), entonces sí tenías derecho a la exención (si reinvertiste antes de 2 años, etc.).

En ese caso, si estás en período de alegaciones, deberás justificar todo eso: escritura de compra, justificantes de residencia efectiva antes de 12 meses y durante 3 años o hasta que te mandaran a Madrid (suministros, correspondencia, domicilio fiscal y de empadronamiento, domicilio de Seguridad Social o de Isfas...), certificado del derecho a vivienda por razón de cargo o empleo expedido por los de rrhh, más justificantes de que la vivienda quedó vacía (de nuevo, suministros como luz y agua sin consumo, etc), escritura de venta y de adquisición de la nueva...