Hi Rider,
i used to fly there for three years, i suggest you start using your girlfriend and start learning icelandic, not as hard as it seems once you get to it and got someone to speak to.
i know Astraeus is doing a wet-lease for iceland Express (B7373 + B757), but I'm not sure whether they will need people, but I believe that a suitable TR will help you if you want to join them.
Then you also have Bluebird Icelandic, cargo company with 737, the requirements are rather lower but again a TR is required.
As for small operators I'm not so sure, been out of the ice pit for some time, but I wish I'd be back, had the best three years of my life up there.
Hope that puts you on course.
Bless Bless (that means "bye" in icelandic if i remember well)
P.s. you got to be a brave man to be dating an icelandic chick (but so lucky)