Uma das dificuldades da nossa língua provém do facto de ela não ter uma lógica geral. São várias lógicas que se misturam e, muitas vezes, chegam a ser conflitantes. Desde o plural de mão não ser «mães» até a possibilidade de se utilizar majoritário e maioritário ou a evolução do «planum» latino para chão e plano, cada palavra tem a sua história, marcada pela origem histórica e condicionalismos regionalistas. Não adianta tentar encontrar um fio único para interpretar a língua portuguesa, que só se vai conseguir aumentar a confusão.

No caso, porque o plural de sem-terra deveria ser sem-terra? Em primeiro lugar, porque «sem-terras» pode ter sentido diferente de sem-terra.

Depois, vamos ver os exemplos para a utilização da palavra «sem» seguida de hífen. Segundo o dicionário Aurélio (estou utilizando um livro de referência brasileiro), temos como substantivo de dois números (invariáveis): sem-amor, sem-dinheiro, sem-família, sem-lar, sem-luz, sem-nome, sem-pão, sem-par, sem-pudor, sem-pulo, sem-sal, sem-trabalho, sem vergonha. Temos como substantivo com plural em «s» os seguintes: sem-cerimónia, sem-cerimonioso, sem-fim, sem-justiça, sem-número, sem-razão, sem-segundo, sem-termo, sem-vergonhez, sem-vergonhice, sem-vergonhismo.

Portanto, as duas formas são aceitas na língua portuguesa. No caso, considero sem-terra mais próximo das primeiras, pelo que emiti a opinião de que não deveria ser variável no plural.

Cf. contraponto deste texto "Os sem-terras e não os sem-terra".