Вы совершенно правы. Верно: памяти воинов-интернационалистов. Слово памяти управляет в таких конструкциях родительным падежом. Подобные конструкции (памяти кого-чего) зафиксированы не только в электронных, но и в печатных словарях (см., напр.: Лазуткина Е. М. Словарь грамматической сочетаемости слов русского языка. М., 2012).
Очевидно, Ваших оппонентов сбивает с толку управление памятник (кому?) – воинам-интернационалистам. Но это совсем другая грамматическая конструкция.
Запятые нужны: Ищешь, чем завязать свои патлы, или стрижешься сейчас же!
Правильно: память об Анатолии.
Выражение память как у рыбки означает очень короткую, мимолетную память, когда человек быстро забывает информацию. Выражение появилось из-за распространенного заблуждения, что у рыб, особенно аквариумных, очень короткая (около 3 секунд) память.
Лучше: собрать волосы в хвост не как-нибудь...
Тире не ставится, если сказуемое выражено оборотом со словом как. Однако при акцентировании сказуемого (обычно в стилистических целях) тире возможно.
Если имеется в виду "храню в качестве памяти", то запятая не нужна: храню как память.
В общем случае тире после местоимения-подлежащего перед именным сказуемым не ставится. При этом более широкий контекст (который здесь не приведен) может указывать на уместность постановки тире.
