Спасибо, Vamp.
Похоже так и есть,
Добавил в первую программу в конце изменение исходной строки, и память увеливилась:

#include <iostream>
#include <string>
#include <map>


int main(){
    std::string str("12356789012356789012345678901234567890");
    std::map<std::string, int> m;
    m.insert(std::pair<std::string, int> (str, 1));
    str = "0987654321098765432109876543210987654321";
}

$ valgrind --leak-check=yes ./a.out 
==12795== Memcheck, a memory error detector
==12795== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==12795== Using Valgrind-3.8.0.SVN and LibVEX; rerun with -h for copyright info
==12795== Command: ./a.out
==12795== 
==12795== 
==12795== HEAP SUMMARY:
==12795==     in use at exit: 0 bytes in 0 blocks
==12795==   total heap usage: 3 allocs, 3 frees, 212 bytes allocated
==12795== 
==12795== All heap blocks were freed -- no leaks are possible
==12795== 
==12795== For counts of detected and suppressed errors, rerun with: -v
==12795== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)