Reconstruction of wildlife distribution based on poorly-sampled data
The problem of how to infer species distributions from scattered species occurrences is common in ecology, and there exists a number of methods to construct distribution maps. As a start, you should have a look at Species Distribution Models (SDMs) using regressions models or Maxent, and the paper by Elith et al (2009) is a good starting point and a standard reference. SDMs using maxent is now a common approach, which integrates species occurrences as point data along with environmental layers (e.g. temperature, moisture and topography) to predict species distribution maps, and this can also include absence data or "pseudo-absence" data (randomly sampled data from a region of interest). The maxent software is described and can be downloaded here: http://www.cs.princeton.edu/~schapire/maxent/
A common criticism against distributions produced by Maxent is however that they ignore e.g. species interactions, and they only considers the species occurences and the environmental variables that has been included in the model.

In your "Note", you touch upon the issue of detectability, which is an important issue that has received much attention recently. The problem is largest when you only have presence data, and to have real presence/absence data is preferable. Even if you don't have real absenses (the species has been searched for but not found), an estimate of sampling effort in different areas is still very useful, since this means that you can at least evaluate whether absenses is due to "real" absense or lack of sampling. In your case, the movement paths of characters could be used as a measure of spatial "sampling effort". The main issue with detectability in studies of distribution of species trends is if there is trends or bias in detectability, which means that apparent changes over time or patterns in distribution might be due to differences in detectability and not real differences between areas or over time. This could for instance be the case if observers are more likely to spot a species in one type of habitat (open savannah) then in another type of habitat (closed forest). Useful starting points for issues of detectability are Dorazio (2014) (technical though) and Kery et al (2010).