I suppose it all depends on just who your ancestors were. In previous centuries, if you were wealthy and/or had political power, you had a far better chance of having your details recorded (eg church records of births, deaths, marriages, or your name and that of your father, perhaps your wife, recorded in a legal document) than if you were poor.
Also, some places were more diligent at keeping records than others. There are some remarkable documents still surviving, from which huge amounts of genealogical data can be retrieved. Some of these ancient 'documents' are actually carved into stone! Most of this stuff is now stored in museums and the like, but they are accessible to researchers, photographs have been taken of them, they've been published on the WWW, books have been written about them - if you know where to look, there's information and confirmation just about everywhere. I might not be able to get it into my hot little hand, but a photo of it does me just as well.
Way back when, when the population was much smaller, and there was a King (call him a Chief, or a Leader if you will) governing an area not much larger than, say, a modern city, it was much easier to be acquainted with or related to a king than most people in today's world. Those '7 degrees of separation' had much more meaning then than now.
Also, it was much easier to go from rags to riches than it is today. Just as easy to go from riches to rags, too - and perhaps see-saw back and forth, all in the matter of a couple of generations! I have several such instances in my family tree. It mattered a lot more then who you supported in a political matter - you could end up fabulously wealthy and powerful, or you could end up losing your house (castle) and your livelihood - if not your head! - if you backed the wrong political horse or 'your side' lost a battle.
Yes, trade was pretty world-wide (as it was known then) as it is today. For example, the Romans had 'business contacts' all the way from Northern Africa, through the Middle East, all the way through both Western and Eastern Europe, to England and beyond, and via Asia Minor (covering modern places like Turkey, Iran and Iraq), and even across to
China. As now, it wasn't unusual for a 'travelling salesman' to decide to settle in a place far away from home, and to marry somebody local, and have children who might also inherit the 'travel bug' and do likewise.
A petty Roman official, sent to look after some impossibly remote outpost, could easily get lonely and marry a local girl. He'd have to notify his superiors in Rome of the event, of course, and generally keep them informed. The Romans were very good at record-keeping. If the girl he married was from, say, from the tribe of the Franks, or the Huns, who also kept records, then it's entirely likely that amongst her ancestry were Vikings, or Turks - because there was a lot of interaction amongst all those groups.
It's too easy for us now to forget that, for instance, the last Pharoahs of Egypt were actually Greek, and when they weren't busy marrying each other, they married into families from all over their considerable domain, and neighbouring ones like Syria, parts of what is now Pakistan, and further east - or north-east, towards modern France, Germany, Bulgaria etc.
When you look at the wider picture, it's easy to see just how widely genes were spread! It only takes one person of, say, mixed Greek/Roman/Turkish ancestry to marry another of, say, French/Russian/British blood and you've got an almighty conglomeration of genes.
Speaking of documents and the like - I've been astonished to discover just how much can be learned from, say, an illustration in a manuscript, or from a statue, or a tomb effigy - much as we get today from an old gravestone which might record the names and dates of a man, his wife, and the names of his children - sometimes the names of his parents. This is what I call really solid evidence.
I've had some extraordinary luck, really. There is one case where I stumbled across a picture on the internet of the interior of an old church in England. There was a bad photo, and a short legend which mentioned a family name which was vaguely familiar - I think it was the maiden name of somebody's wife. Well, I emailed the
PR person at that church, requesting a better photo of the 'interesting bit' and any information they might have on the person concerned, and his family.
The following morning (TRUE!) I got a reply - complete with photo and pages and pages of information from the church's archives. It seemed my 'obscure little woman' came from a very important family indeed, numbers of whose names occur in legal documents and the like. It's hard to refute evidence like that. This particular 'little woman' was born in the 10th century, and her line to the present day is well documented all the way through. Amazing stuff.
Don't worry - I've come across my fair share of brick walls, too!
Back to my point, however. Is there any solid evidence of Joseph of Arimathea (et al) having gone to Britain?