Consider Poland?
I know this, because I work for a large multi-national, and my boss always complains when he has to deal with relocating people from non EU countries to Czech republic.
On the other hand, it happens reasonably often, in two years we hired several people from Armenia, Serbia, Russia, Ukraine ...