I think another thing that may help you is to try sending out a few emails to several different schools. Since you used the U.S., I'm sure there would be a few people responding back on what they are normally looking for. Also be blunt with them in asking about the pros and cons of getting a master's in your home country versus in America.
My opinion is that it may be harder for someone to know about the reputation of the schools you went to if you are in central Europe. Don't get me wrong, you may have gone to one of the toughest best schools over there. But a person over here might not realize it. So you may have to go out of your way to emphasize the reputation of where you went to.
I think another thing that is in your favor is that you are choosing to teach history. I'm guessing you will specialize in European history? I would think many universities wouldn't mind someone that is from Europe to teach that. Sort of like an American going to Europe to teach American History. I took a European history class in college and the guy that taught it was British for example.
Given your pretty hypothetical scenario, I would say that your degrees will be accepted in other countries, yes. However, this will be subject to the requirements you had to fulfil for said degree, i.e. the workload, your transcript and your marks.
Regardless of your program of study, as long as your University is accredited by some body recognized in other places then you'll be fine. Another indicator is the structure of the education the United States typically recognizes:
Undergraduate year-1 - Core coursework like Language/Arts/Math/Science
Undergraduate year-2 - More core coursework
Undergraduate year-3 - Junior level coursework, this is when you typically begin to specialize in something you're "Majoring" in
Undergraduate year 4/5 - Senior level coursework, this is when you really specialize in very specific courses (Entire courses dedicated to 1 thing within a subject)
Graduate Master - Transition to graduate work, mostly research based
Graduate Master - Probably Research coursework in your field of study
Graduate Doctoral - Doctoral programs do not always have a master step, but are typically 3-5 more years of graduate work
Graduate Doctoral - Graduate work (at least for me) is almost always research driven. If it is a Terminal Doctorate (MD/DNP/PharmD/DDS/JD) it is 3-5 years plus an internship toward mastery.
If you complete 4 years of Undergraduate and 2-5 years of Graduate at an accredited University, especially in a subject like History, you're probably solid.