"Moins" is not redundant, removing it would reverse the meaning of the sentence:
- "ne soulève pas" means "doesn't raise"
while
- "ne soulève pas moins" means "nevertheless raise".
"En" refer to "légitime et nécessaire", i.e. "ne soulève pas moins du fait qu'elle soit légitime et nécessaire..."
The sentence might be simplified this way:
Bien que légitime et nécessaire, cette question soulève immédiatement une difficulté qui semble insurmontable.
Insoluble questions are often little appreciated but the context should better explain why the author put in opposition "legitimate and necessary" and "insurmountable". Here is a guess about what (s)he had in mind:
Bien que la question s'impose (et mériterait d'avoir une réponse satisfaisante), elle semble cependant insoluble (et voici pourquoi on ne sait pas y répondre...).
Note that "pour ... que" is used in a rare, literary way to introduce a concessive clause (similar to even though or despite in English), like this excerpt from the TLFi pour entry shows:
C.− [Marque l'idée de concession]
...
2. Pour + adj. + que (+ subj.). Il (...) lui jura que, pour grand que fût son amour, son amitié l'emportait de beaucoup encore (Gide, Caves, 1914, p. 763). Ce succès, pour modeste et incomplet qu'il fût, m'apparaissait comme une première étape vers la victoire (Joffre, Mém., t. 2, 1931, p. 61). Je me sentais perdu et, pour absurde que cela paraisse, j'eus un bref mouvement de désespoir (Bosco, Mas Théot., 1945, p. 108).