Может быть, и без первой запятой обойтись? Память о той поистине народной войне...

Вы совершенно правы. Верно: памяти воинов-интернационалистов. Слово памяти управляет в таких конструкциях родительным падежом. Подобные конструкции (памяти кого-чего) зафиксированы не только в электронных, но и в печатных словарях (см., напр.: Лазуткина Е. М. Словарь грамматической сочетаемости слов русского языка. М., 2012).  

Очевидно, Ваших оппонентов сбивает с толку управление памятник (кому?) – воинам-интернационалистам. Но это совсем другая грамматическая конструкция.

Если частица пусть или да употреблена всего однажды в начале предложения, она может быть объединяющим элементом, например в предложении Да припомнятся Господом беззакония отцов его и не простится грех матери его! Если же частица употреблена дважды, то у каждой части она своя, и в этом случае она уже не объединяющий элемент, например: На суде да окажется он виновным, и сама молитва его да будет ему в грех!