First of all let me say that this is an excellent and well researched question.
A quick recap from Wikipedia is handy:
Outside the mainland of Afro-Eurasia, [...] megafaunal extinctions followed a distinctive landmass-by-landmass pattern that closely parallels the spread of humans into previously uninhabited regions of the world, and which shows no correlation with climatic history [...]. Australia was struck first around 45,000 years ago, followed by Tasmania about 41,000 years ago (after formation of a land bridge to Australia about 43,000 years ago), Japan apparently about 30,000 years ago, North America 13,000 years ago, South America about 500 years later, Cyprus 10,000 years ago, the Antilles 6000 years ago, New Caledonia and nearby islands 3000 years ago, Madagascar 2000 years ago, New Zealand 700 years ago, the Mascarenes 400 years ago, and the Commander Islands 250 years ago. Nearly all of the world's isolated islands could furnish similar examples of extinctions occurring shortly after the arrival of Homo sapiens, though most of these islands, such as the Hawaiian Islands, never had terrestrial megafauna, so their extinct fauna were smaller.
Other than over-hunting, several other causes have been advocated.
This is ruled out both by the bigger and clearer picture that we have (which includes extinctions over 50.000 years) and by several examples were extinctions did not occur necessarily with climate change (the best example being the survival, until mid Holocene, of a Mammoth in an Alaskan island, see. Guthrie R. D., 2004, Nature, 429, 746). Indicators of global climate change do not show any correlation with extinction patterns.
Over hunting is the other hypothesis, and currently the most accepted one.
The survival of megafauna in Eurasia and Africa to present day is explained by the fact that these animals co-evolved with our ancestors over 2 million years, and had time to develop means to defend themselves. On the other hand, megafauna in the other landmasses was naive to unknown and relatively small sized humans, which might have proved fatal.
The lack of killing sites is explained with the exceptional rapidity of the extinctions. In New Zealand, for instance, the extinction of Moas was more rapid in the North than in the South Island, because of different human population densities. Accordingly, in the North it's more difficult to find butchery sites, whereas in the South more than 100 have been found already.
Other causes are summarized in Burney and Flannery 2005.
Burney D. A. and Flannery T. F., 2005, TRENDS in Ecology and Evolution, 20, 395
In their recent study, Turvey and Fritz 2011 claim that their results:
are generally consistent with the hypothesis that large mammals have been disproportionately vulnerable to extinction since the end of the last glaciation.
Turvey S. T. and Fritz S. A., 2011, Phil. Trans. R. Soc. B 366, doi: 10.1098/rstb.2011.0020
Johnson 2002 studied the effect of body mass and reproductive rate in relation to megafauna extinctions, in the Americas, Australia, Madagascar and North-Eastern Eurasia. He finds that there is indeed a trend with body mass (higher body masses more likely to go extinct) but also with reproductive rates (low reproductive rates more likely). Because the two are related (this is an assumption he derives from extant species) it is impossible to disentangle them.
Among the extant species (remember that we are talking about specific areas of the world), some are massive enough and had low enough reproductive rates that they should be extinct according to the patterns discovered. The traits they share shelter(ed) them from human contact; they are one or more of:
- live at high latitudes
- live in closed habitats (e.g. dense jungle)
Johnson C. N., 2002, Proc. R. Soc. Lond. B 269, doi: 0.1098/rspb.2002.2130
The best evidence so far is to be found in Rule et al. 2012. They analyze the occurrence of Sporormiella fungal spores (which derive mainly from the dung of megaherbivores) in mud cores spanning the last 130000 years from Lynch’s Crater in Queensland, Australia. Their data showed that megafauna happily survived two major changes in regional climate, only to disappear about 41000 years ago, when climate changes were minimal. The Sporormiella spores disappear before the increase in charcoal and the transition from rainforest to fire-tolerant vegetation, supporting the idea that hunting alone eliminated the megafauna, and that the subsequent change in the flora was a consequence of the elimination of browsers and an increase in fires.
Rule S., Brook B. W., Haberle S. G., Turney C. S., Kershaw A. P. and Johnson C. N., 2012, Science, 335, 1483, doi: 10.1126/science.1214261