Brands can be tough to trace if you don’t know where the horse came from.
Here, out west, most states are brand states and require registration of brands making it a bit easier as you can contact the local brand office or look up brands on the website. Farther east, from what I’ve been told, brand registration is not the norm making them harder to trace. Which makes no sense to me but I guess some people brand anyhow.
Plus there are states like Texas who register their brands by county.
I would start with those states you know the horse had been in and of course registration papers are a good place to start. But I am guessing if you had those you would not be here asking.
Good luck! Hopefully, someone recognizes.
(Location of the brand on the horse helps too. Example Left hip, right shoulder, left jowl, etc.)