While the whole Schengen area may not allow you to work everywhere, the core EU area pretty much does[1]. Of course you may have to do some paper work, but, generally, if you have a job offer from another EU country, you will be able to take it without having to worry about getting a visa.

Nordic countries also have their own passport union, so a Finnish passport, for example, will let you go and work in Iceland or Norway pretty freely.

I would imagine there are be some other regions that have similiar agreements. I think that the Commonwealth at least used to have some benefits for its citizens, but I'm not sure how much of those remain.

[1] http://www.citizensinformation.ie/en/moving_country/moving_a...