To answer this question, think about the purposes for which records were created.
Official record sets kept by goverments such as the BT 26 lists of passengers arriving in the UK between 1878 and 1960, like many of the records we re-purpose for genealogy, were kept because they were mandated by law. Learning more about the laws in effect at the time can help us determine what record sets our research subjects might have records of our ancestors.
Another driving factor for keeping records is keeping track of money, such as merchant's account books, company records, and the like. We can look for clues in libraries' special collections, in company archives, in museums, historical societies, and other repositories.
Records of people moving from one country to another might also be found in manuscript colletions, in the form of diaries, or as published travelogues.
It can be challenging to find records like this because the records themselves can migrate along with people, and there's no telling where they might end up eventually. You could try looking for published works in WorldCat or via JSTOR and Google Scholar; examine the bibliographies carefully to see what sources the book and article authors found and where those sources were found.
Look for research guides and finding aids from archives like those found at TNA and published works on how to trace migration.
You can search for manuscript collections and other archival material by searching at TNA's Discovery website, which includes records held by other archives, at ArchiveGrid, the companion site to WorldCat, and the Library of Congress' NUCMC (National Union Catalogs to Manuscript Collections.
For an example of what type of records can be found before official government recordkeeping is mandated, look at the article Ships Passenger Lists & Naturalization Records at Olive Tree Genealogy, the website created by the late Lorine McGinnis Schulze. In the section Immigration Projects you can find record sets transcribed by volunteers. This list is largely about the US and Canada because of Olive Tree Genealogy's focus -- the point is to look at what kind of things Sculze and her volunteers were able to discover.
To find how-to articles, published transcriptions, and other articles from publications dedicated to genealogy, use PERSI, the PERiodical Source Index from the Genealogy Center at the Allen County Public Library. PERSI used to be part of Heritage Quest, was hosted in part by Ancestry (the old printed volumes), was available for a while at findmypast, and has now come home to a new website at the Allen County Public Library.
PERSI links:
This is the kind of inquiry that takes some digging. Whenever you find a record set that doesn't cover the time period or geographical area that you need, look at the type of record it is, and ask Does something like this exist for my area of interest? and How can I find those records? Research the topic and see what you can find. One research starter which might help is to ask "How many?" questions such as How many British subjects returned from the West Indies in the year 1800? Answering those questions may lead you to interesting sources. Even if there are no detailed, official lists of British Subjects returning home for the period, you may be able to find discussions about the topic in newspapers, in agency correspondence, or published government reports.
Don't neglect the projects done by people who are studying aliens/non-subjects, because their work can give valuable insight into ship movements and related material. Consider that whenever a ship arrived in the US or West Indes, it had to carry something or someone on the way back. You may not find lists for the inbound passengers, but you may be able to establish time periods for their return to Britain which will help you set parameters for research in other record sets.
You may not find a particular person in these scattered records, but you might get a "lucky dip". You can't know unless you look.
Resource List