According to http://www.colonizationfans.com/lost-city-rumors.html :
"When an unskilled scout enters a native settlement, there is a chance that he will be upgraded to seasoned scout."
Note that they say Native Settlement not Lost City Rumour.
Perhaps we could implement this as "visit 5 native settlements and you will gain the necessary experience". Number can then be tweaked.