I don't know if native populations change significantly in LA (I've played all my games EA so far, I think), but in EA I seem to find enough populations with stealthy priests (usually they're also low mages).
Amazons, Tribal poptypes with mages and druid provinces all become much rarer in later ages. I'd quess trolls and cavemen and such disappear completely. Hoburgs of later ages have Hog Knights and such, and I'm not sure if they have those cheap priests any more.