Matthew, unfortunately, the internet abounds with all sorts of - what I would call, "fantasy trees." There are a lot of links from descendant to ancestor that are wrong and these are copied and shared as internet fact.
Really, the only way that you can verify all of your ancestors is to do the research and check them, one by one, generation by generation. Make no mistake, it is a lot of work. Be prepared to spend months, years even, to validate your tree. I wrote about this in March in a post Have you audited your ancestors? Ideally, you want, for each person in your tree to be genealogically defined. This means that you have a source that proves who their children were, who their spouse was, and who their parents were. For each profile that you can genealogically define that is connected to you through an unbroken chain of profiles that are each genealogically defined, you can definitively say that these are your ancestors. Other ways to validate would be through all male line DNA tests.
Most often, it is not possible to source all of your ancestors to the level of being genealogically defined. And in these cases one must be a bit of a detective and look at all of the information available. If you know for sure that your ancestor was James Zainsworth born 1780 and his father was William and you find a James Zainsworth and you find a William Zainsworth born in the same small town in 1750 and there are no other Zainsworth families, William is probably the father of James.
But if your ancestors were James and William Smith and they were born in different towns, then there really is no way to validate a connection like this.
I'd recommend you start with your parents and their connections to your grandparents. I'd enter the data on your parents profiles when they were born, who their parents were, and put in the source that proves it. Even if their profiles are closed or unlisted, put the source in now. Your grandchildren will thank you for it in 30 years.
Then go to your great-grandparents. Do you have source documents that prove they were the parents of your grandparents? Do you have documentation for their marriages? Then on to the 2x great-grandparents. As you can see, grandparents are easy, but by the time you get to 3x great grandparents, you're dealing with 32 individual profiles. To link their parents, 64 profiles, and your 5x greats, 128 profiles. Just to validate your ggg-grandparents, your 4x greats, and your 5x greats, you'll need to analyze, research, and then document 224 profiles.
From my own ~ 23 years experience in genealogy I can say that most people don't put in the work. So when I meet someone and they say that they are descended from Charlemagne, I smile and look interested but the chances are, they really have no idea.
In answer to your question about the skepticism of others - the only way to beat that is to do the research.
I'm not so sure about, you wrote:
And, more for my curiosity's sake, what documentation would an immigration office require?
What sort of immigration office are you referring to? If you can supply some more details it would be helpful in answering your question.
I hope this answer has been helpful for you. In a nutshell, it is going to take work, a lot of work. So be ready and good luck!