30th cousins = 29x great grandparent. At a rough average of 30 years per generation, then the common ancestor would be born about 1100-1200 AD.
IMO, information from before 1600 becomes rather speculative, and while it can make for a good story, I don't necessarily trust that the connection is genetically valid. Even if the records exist, and if people didn't have similar names that caused confusion, the possibility of an unpublished non-parental event (NPE) adds up for each generation. An extra-marital affair, adoption or outright fabrication will likely have occurred at least once in that chain.
On the plus side, if you both come from the same part of the world you're likely already 20th+ cousins with everybody else in that area, even if you don't have the documentation.