I think the scouts upgrade sometimes when you visit native villages. At first I thought it was only in villages were seasoned scout was the village specialty, but I think I remember it happening in a village where that wasn't the case. Maybe it's just one of the bonuses you can get from talking with the chief.
[edit]re: vet soldiers
So the only way to get a vet soldier is from Europe? That's odd, they probably should have just removed the veteran soldier specialty since they included CIV experience and promotions. It's kind of a weird double system now. At the very least they should rename them to "trained soldier," or maybe "officer"? Anything but "veteran," as veteran is clearly related to combat experience, which all your units get after fighting.