У меня просто была эта проблема, и для меня это было потому, что я связывался с версией разработки для библиотеки, но мой тестовый код собирал более старую версию, установленную системой. Изменения были достаточно тонкими, чтобы связать их и запустить без каких-либо явных проблем, но Valgrind обнаружил странные утечки. Использование ldd вместо valgrind подтвердило, что он подобрал неверный файл библиотеки. Установка LD_LIBRARY_PATH корректно исправила его, хотя правильное решение - увеличить версию библиотеки, поскольку она, очевидно, больше не будет обратно совместимой, если это произойдет.
Я также видел эту проблему, когда объект не был уничтожен должным образом, например, класс с virtual функциями, в которых отсутствует деструктор virtual. Когда класс помещается в указатель на базовый класс, а затем уничтожается, запускается только деструктор базового класса, пропускающий все, что размещено в производных классах, например, std::string экземпляры в вашем примере. Подсказка заключалась в том, чтобы проверить, какой класс использовал утечку string, и следовать иерархии классов обратно к базовому классу и убедиться, что у нее есть явный деструктор virtual, даже пустой. Я предполагал, что они были неявными, если в классе есть virtual функции, но, очевидно, нет, и GCC не предупреждает вас об этом.