Australia did have some megafauna. Thylacoleo was a masupial lion (101- 130 kg) roughly comparable to the weight of a lioness. They died out during the pleistocene and were Australia's largest known carnivorous mammal. There were also grazers such as Diprotodon (a kind of giant wombat), Palorchestes, plus a few others nearly all of which died out in the pleistocene

Just for the record (sic) accurate records were kept in Great Britain from 1837 (Civil registration bill being passed in 1837) and France from shortly after the French Revolution. This is aside from the parish records some of which (especially the Methodist ones) carry a great deal of detail. The best of these latter records record not just the names of parents but the mother's maiden name, father's occupation, location (ie farm name for instance), and date of birth if it differed from that of baptism. In England law was passed in 1538 by the then new Church of England making the keeping of such records a legal requirement, though most parishes did not enact it until 1598 and even then records were patchy (not to mention disruption by Civil war in the 17th century). As with any sytem there will be those who slip the net.

It largely depends on when. During the middle ages under the feudal system it was difficult for all but itinerant workers (tinkers, travelling merchants, etc.) to move but as the feudal system collapsed this changed. During the English civil war many ordinary people moved about, travelled to the new world etc. Also often occupation dictated movement. My Potter ancestors generally stayed put but my miner ancestors moved as mines ran out of coal, lead, tin or whatever they happend to be mining.

As a companion to this article I loved "An illustrated book of bad arguments" by Ali Almossawi - Straw men, Equivocation, appeal to fear. it's all there.