Вывод проверил на разных входных данных - все верно. Что за @Убедись, что список lines в нужных местах содержит операции REMOVED c нужными строками.@
if (file2line.isEmpty()) {
                    lines.add(new LineItem(Type.REMOVED, file1line));
                }
что не так в этом условии?