Oficialmente, recomenda-se para o feminino de todo-poderoso todo-poderosa e, nos plurais, todo-poderosos e todo-poderosas, em que todo parece estar com sentido semelhante ao do advérbio muito. Pessoalmente acho um disparate, pois então não poderiam existir toda(s) contente(s), equivalentes de muito contente(s), e devia dizer-se todo contente(s), com o todo também invariável. O mais extraordinário é que todo nunca aparece registado como advérbio, e portanto não se percebe como é que se mantém invariável nas diversas flexões de todo-poderoso. No meu entender, só que não é legal, devia ser todo(s)-poderoso(s), toda(s)-poderosa(s), com hífen ou não.