Shiur I heard from Harav Gedalia Dov Schwartz, Shlita. All inaccuracies should be attributed to me. As always, each case must be investigated by a capable posek.
Kiddushin 72b says: Amar R' Yehuda amar Shmuel [Rashi: The mishna that implies only Bavel is meyuchas] is the opinion of Rabi Meir, but the Chachamim say all lands hava a chazakah of Kashrus.
The mishna on 76a discusses checking four mothers. 1) Do you need the check for issurei kehuna? 2) Do you need to check when someone comes to a community and wants to marry a Jewish girl?
76b 3rd line says: Amar R' Yehuda amar Rav this [Rashi: the stam mishna that you must check the family] is the opinion of Rabi Meir but the Chachamim say all families are bechezkas kashrus.
Note this is talking about families, and on 72b is talking about countries.
Ran Kiddushin 31b s.v. Vgarsinan (it's above garsinan) Amar R' Yehuda amar Rav this is the opinion of Rabi Meir but the Chachamim say all families are bechezkas kashrus.m said R' Chama in the name of Rav if there was irur you must checkafter her - even according to Chachamim. Rashi explained Irur that tw witnesses mentioned an impurity but they did notgive actual testimony, just rumor (yetzias kol) and Rambam (IB 19) this is when two testify that one of the psulei kahal or psulei kehuna married into the family . And it's possible when we need krias irur only when there is a suspicion of mamzerus because Yisrael recognizes mamzeirim among them but for chalal you must check even without irur, and thus paskened Rambam. Others say to Chachamim, like whom we pasken, even for chalal we don't have to check unless theire is irur.
Tur Even Haezer 2 (p. 4b 3rd line) says to Rashi & Ramah you must check someone if they don't have chezkas kashrus. Tur feels you don't need to because all families are ksheirim, and Rabbeinu Tam says you only have to check for Kohein.
Beis Yosef (5a s.v. umah shehichria rabbeinu) - he argues on Tur and says for chalalus you must check even without irur.
Shulchan Aruch 2:2 Kol hamishpachos bechezkas kashrus. Beis Shmuel 3 at end says ..therefore we should be machmir that someone who is not known to us we must suspect he's a mamzer.... Achronim bring from Tosfos Yevamos 47a s.v. Bemuchzak, that when someone comes and says "I'm Jewish" we believe him...that rov who come before us "betoras yahadus, yisraelim heim." But does it hold true when it flies in the face of facts? To show how concerned in Europe they were of mi sheba, a stranger, see Beer Heitev 4: "The Beis Hillel (acharon, not the tana) says one who came from another land wheter it's a man or woman, a young man or young woman, a widow or widower, needs a proof that he is Yisrael. Even if he acts like "das yisrael" and speaks our language and knows the "tuv hayehudim" still needs a proof; this is the takana of Medinos Lita that one may not be mesader kiddushin unless there is a proof he is Jewish and from which family." This is talking about one person who coes alone, not with a family. The Mahrit, who was a Sfardi from Kushta (Constantinople), also says this. Pischei Teshuva 3 brings Shaarei Hamelech who strongly disagrees on the Maharit and says the mechaber holds one who comes from another land is believed because mishpachos have chezkas kashrus, and not like the Beis Shmuel says.
According to Rabbeinu Tam above, who seems to be a big meikil, the Otzar Haposkim (p. 90) brings Kiryas Chana David that we only believe him (and let him marry a woman from our community) only if he is acting kedas Moshe veYisrael, but if not we certainly suspect him.
Aruch Hashulchan 2:12 mentions other rishonim who are more lenient than the Ramah: Ramban, Ra'ah, Ritva in Shita Mekubetzes Kesuvos.
Regarding Russian immigrants who relatively recently arrived, Rav Shlomo Kluger in Haelef L'cha Shlomo relies on shitos that kol aratzos bechezkas kashrus. I sat on a Beis Din with other rabbonim asking Russian imigrants about their grandparents, who spoke yiddish, there was one woman whose maternal grandmother had an oven to bake the matzos for her neighborhood.
Response to a question: A mesader kiddushin must know the people. Brod Rov (R' Kluger) relied on a notarized affadavit because if you falsify it, you're perjuring. Because with a thorough investigation it is milsa d'avida ligluyei like Yevamos 39 - not only what he says, but it will come out in an investigation.