I have experience teaching in eastern Europe as well. It's been hit-or-miss. It's best if you're flexible and don't fixate on any particular location.

If you need a visa and work permit, it really complicates matters: I highly recommend acquiring European citizenship if at all possible. (I did, which had the side-effect of immersing me in genealogy as a hobby.)