Как решить задачу поиска повторяющихся строк без использования Counter?

Используйте два множества: seen для встреченных строк и reported для уже выданных повторов. Это позволяет вернуть каждую повторяющуюся строку один раз без Counter.

Здесь порядок результата соответствует моменту обнаружения второго вхождения:

def repeated(lines):
    seen, reported = set(), set()
    result = []
    for line in lines:
        if line in seen and line not in reported:
            result.append(line)
            reported.add(line)
        seen.add(line)
    return result

Ожидаемое число операций с хеш-таблицами — O(n), память — O(u) для u разных строк; дополнительно учитывается стоимость хеширования текста. Если нужны количества, используйте обычный словарь с counts[s] = counts.get(s, 0) + 1. Нормализацию пробелов и регистра задавайте явно.