Com efeito, o Dicionário Eletrônico Houaiss regista, como feminino de condestável, condestablessa (e não "condestabeleza").

Etimologicamente, condestável é a «lexicalização no lat[im] med[ie]v[al] do s[i]nt[agma] nominal comes stabŭli, "encarregado da estrebaria", por meio da seguinte sequência fonético-evolutiva: *comitemstabuli > *condestáble > condestabre ou condestável; ver conde e estábulo; f[orma] hist[órica] 1387 condestabre, sXV cõde estabre, sXV comdeestabre».

Ainda existe a variante condestabre, mas a forma preferível é condestável. Era, «no sXIV, posto militar de maior graduação no exército de Portugal, abaixo apenas da suprema chefia do rei»; «nos sXVII e XVIII, cabo que apontava e dirigia a artilharia da milícia, em Portugal e no Brasil colônia; chefe dos artilheiros nas fortificações e praças de guerra»; «no sXVII, a partir do reinado de D. João IV (de 1640 a 1656), título honorífico de alguns dos maiores senhores da corte (infantes, duques, marqueses), que conservavam levantado o estoque ("espada") diante do rei nos juramentos régios e dos príncipes»; e, numa derivação por metonímia, «dignitário que tinha tal graduação militar ou que ostentava tal título».