You can't find records if they don't exist.
Genealogists love it when all the pieces exist, and they solve the puzzle. If only that were always true, how happy we'd be. It isn't true, but you can still be happy - if you're prepared to accept facts. Repeat after me: "Some records don't exist."
But why not?
The first reason may be resolved some day when the record that does exist gives up its secrets. Poor penmanship, wretched microfilm, language difficulties, illiteracy, bad spelling… each of these can cause a record to "disappear," in the sense that no one reading it gets anything relevant from it.
Some records do exist, but they are just plain wrong. Let me provide an example. We find Johnny buried on January 5, 1859, age four months. In the baptism register we have Johnny christened on October 10, 1859, one month old. Perhaps the minister made the sort of human error we can all make, forgetting to change his mental year to the new date. Once we figure that out, we see that Johnny was born in September 1859, and buried in January 1860. So the record was there, but it was wrong.
The same thing occurred sometimes where the clergyman confused the names of married parties and witnesses, and the best man is entered as marrying the bride, while the groom looked on. I have seen this, and more than once!
So far I've mentioned records that exist but mislead. There are also cases where there was no record produced at the time and therefore we're seeking in vain. As colonies, the Maritime Provinces and Newfoundland were casual about such things as passenger lists, so thousands of newcomers, mainly from the British Isles, turned up here by means unknown.
Some officials did not consider people from Ireland or Britain immigrants at all, but simply British subjects moving from one jurisdiction to another. This may have lead to a few of those tales of ancestors who "jumped ship" as an attempt to explain where the family came from.
If your ancestors were Baptists, there are no baptism records because they didn't practice infant christening. If ancestors died in the country, out of reach of a resident clergyman, they were probably buried in a plot on the family land, or in a community burial ground for which no one kept written account. If no one entered the death in a family Bible, then there may be no record to find. Perhaps you can approximate the time of someone's death by finding probate records or land sales.
And does it matter whether great-grandfather Jones died in 1877 or 1880? Presumably you have established that he is your ancestor, which is what matters. Simply enter in your family record that he died between March 1877, when he witnessed a deed, and the date the census was taken, April 1881.
The most common source of genealogical angst, in my experience, is when people can't find any record of the marriage of ancestors who had large families. Ask yourself this question: How many neighbours or acquaintances live together nowadays and raise children, and you don't actually know if, or when, they were married? Why would people back then be any different than we are now?
Think how easy it would have been to pass yourselves off as a married couple at a time when immigration was taking place on a massive scale. You didn't want to risk bigamy, but you were fleeing a failed marriage and met up with someone else in Minnesota in 1870, or interior BC in 1890.
You became a couple, and if any neighbourhood Nosy Parker asked, you'd smile and say, "Oh, we were married back east before we came out here." As long as no one from back home turned up to spill the beans, you were scot-free. It happened.
So don't think there will always be records. Perhaps what you can't find, never was. Quel dommage! You'll live; I know I did.