Well, it depends on what exactly you mean by "records".

If you mean are there regions and time periods where we lack contemporary, first hand written accounts about society and what went on; absolutely. Prior to about 1500, there were large stretches of Africa, the Americas, Australia/Oceania with non-literate societies. So, any accounts that purport to tell of events that happened in 1300 in the region that became Venezuela (for instance), come from oral traditions that had to be passed down for a few centuries before the possibility of being written down.

You might also have a broader definition of "records" that includes oral traditions/folkore or even modern archaeological data as sources of knowledge about the past. In that case, examples of societies without such records would be much more sparse.

There are a few factors that could frustrate the possibility of using archaeology as a source of information. If a society had a lifestyle that left behind a very light material footprint (i.e. nomadism or semi-nomadism), it would be harder to collect and analyze such material. If a society lived in a climate region that was bad for preserving materials that they used (e.g. a tropical rainforest). Or, if the habitation sites of a society have been severely disturbed by modern construction, warfare, or vandalism, and so the context of the materials has been irreversibly altered.

There is also the possibility that local politics or the concerns of local stakeholders would mean archaeological investigations are unwanted and are not allowed to happen.

Turning now to Oral History or Folklore, it is also possible for these sources of information to be lost. For a society's entire corpus of oral tradition to be lost, it would most likely follow the loss of the language these traditions were spoken in. This could either happen through the death of language speakers, through disease, famine or warfare; or it could be the result of deliberate schemes of cultural assimilation (think native boarding schools in US and Canada).

Is it likely that there are examples where archaeological and oral history constraints combine to leave us unable to generate any historical knowledge about a given society? There probably are cases like these within the past 1000 year timeframe, but I can't name a specific example at the moment.