Curiosity got the best of Dad, and he decided to go through and pay for a few birth certificate pulls from Scotland on some of our relatives. This developed into us going hog-wild for a solid week, collating everything up and then.. throwing it away and starting again.
Dad's been into the process for ages, and it's safe to say the tools have gotten a lot better. Many of the records, unavailable except in person when a distant cousin of ours was doing research into our convict heritage in the 80s, are now digitized and available online. Court proceedings from the Old Bailey are available, searchable, and downloadable for free (not originals, I'm assuming, but type-written transcriptions which are then OCRed into a computer readable format). A contractor to the Scottish government will provide scans of old parish records for you for a fee. And there's entire forums of others who are also interested who may have the information you're missing!
It's been put into our heads from another member on a Genealogy forum who contacted my sister after she posted for help, that we were related to one group of Frasers from Scotland. Unfortunately, we have almost definitive proof that we're in fact related to another group. This highlights a problem with sites like Ancestry.com (which is an absolutely fantastic resource, by the way, if used correctly) making Genealogy more accessible to people with $25, a couple of hours and a few thousand mouse clicks to spare.
They're inherently populated by unthinking shit heads.
There are huge numbers of people who have, in their trees, what we thought was our Great^6 Grandfather, but have him as dying in Ontario, Canada. It doesn't take very long at all to discredit this reference, but people just click the button and slam it into their tree anyway.
So we started compiling the family history again, comparing it to what we had years ago, and getting proof for everything. It's highlighted a number of mistakes and misunderstandings, particularly about the first fleet ships and the convict trade prior to the establishment of the Australian colony.