Understanding how people move within a geographic area, e.g. a city, a country or the whole world, is fundamental in several applications, from predicting the spatio-temporal evolution of an epidemics to inferring migration patterns. Mobile phone records provide an excellent proxy of human mobility, showing that movements exhibit a high level of memory. However, the precise role of memory in widely adopted proxies of mobility, as mobile phone records, is unknown. Here we use 560 millions of call detail records from Senegal to show that standard Markovian approaches, including higher-order ones, fail in capturing real mobility patterns and introduce spurious movements never observed in reality. We introduce an adaptive memory-driven approach to overcome such issues. At variance with Markovian models, it is able to realistically model conditional waiting times, i.e. the probability to stay in a specific area depending on individual's historical movements. Our results demonstrate that in standard mobility models the individuals tend to diffuse faster than what observed in reality, whereas the predictions of the adaptive memory approach significantly agree with observations. We show that, as a consequence, the incidence and the geographic spread of a disease could be inadequately estimated when standard approaches are used, with crucial implications on resources deployment and policy making during an epidemic outbreak.