I don't think this axe can be found with northern cultures (the tribes, especially the middle and the eastern one). They seem to carry only handaxes. If they do have possibility to spawn other axes, the chance of obtaining them is so low it is not worth looking for anyway. However, every other culture, the ones with agriculture (fields around villages), can have it, and restock items about every 3 months or so. If you are in the north, look in Sartola, Koivula or Kiesse villages. I had particularly much luck with Sartola.
I think there are similar rules for punt, though I do have some agricultural cultures which never had punts in my game.