Tony Shalhoub as the taxi driver in Quick Change.
How about any of the Solomon’s on 3rd Rock from the Sun? I don’t think their supposed planet of origin actually exists (?)
I agree. I wish to complain in a whiny voice about the OP excluding this stellar character just because Kazakhstan is a real place. Maybe so, but Borat’s version of it isn’t – e.g.- alleged traditions like the “Running of the Jew”, or Borat’s sister being highly regarded for her work as a prostitute.
Besides, this silly rule also eliminates the greatness of Manuel, the inimitable waiter in Fawlty Towers!
But if my choice is going to be rejected I’ll gum up the works with a character that probably no one’s heard of: Pepe – not from a sitcom, but from one of the best of the “Carry On” movies, Carry On Abroad. Pepe, played by Peter Butterworth, is the hapless owner of a half-finished hotel on the fictional Mediterranean island of Elsbels who must suddenly play host to a busload of British tourists. Not only does he have only half a hotel, he also has no staff – so Pepe must simultaneously be the doorman, the manager, the porter, and the maitre’d, assisted only by his ill-tempered wife cursing in the kitchen. Pepe’s broken English is priceless.
This isn’t a particularly good clip (the actual movie is far better) but it does give you a glimpse of Pepe … 
… And the newsstand owner in Frasier.
It can be. Not that Sean Astin would get my vote, though.
No mention of his theological treatise?
Since nobody’s mentioned Fez, I will. Compared to most of the others, his shtick was reasonable rather than over-the-top approaching psychotic. The show used him well and progressed the character in a realistic way. Heck, he practically took over the show after Eric left.
One of the writers said they named him Fez as an initialism of Foreign Exchange Ztudent.
‘Exchanged’ from absolutely anywhere.
ps: I’m always impressed with his acting when I see him currently playing a tough cop without an accent (in… ?.. one of those ubiquitous cop shows).
How about the Coneheads? They weren’t really from France.
Simka Dahblitz, but not the Simka Dahblitz.
[Deleted - redundant]
How about Mlepnos from Brooklyn 99? Only shows up a few times, but they were memorable. Weird, strange traditions, and just a hint of mystery about him.
Areola from Not Another Teen Movie.