Take a course in European history, learn about all the wars, genocides, forced and unenforced migrations, plagues, etc. and even more mundane thinggs like intermarriage outside of immediate community ( very common amongst nobility ) and tell me again with a straight face you believe people have remained in the same place for thousands of years
They may have recognized your wife as “foreign” based on a number of things. The most obvious being language, But it could have also been dress, makeup, demeanor etc.