Well, I'm back. As a follow up I'll cover a few points that may be of interest to people.
To cover the main topic of the thread, I found a box (of 5 rolls) of 120 velvia in a photography shop in Reykjavik called Hans Petersen on Bankastraeti (oposite the old government building). The cost was 4300 Kr, which being over 4000 Kr meant I could claim back some of the tax (550 Kr), but was still twice what I paid in the UK. They also had a few boxes of black and white films in 120 as well. In future, with more time allowed for planning, posting film ahead is probably the way to go.
Now, on to some of the other points raised. (I guess this all really belongs in the 'locations' forum now, I only asked in the colour film forum originally as it seemed more active and likely to get a quick answer, and it was a question about film after all. Can the thread be moved to another forum somehow ?)
The comment about going by ferry is actually quite valid. For anything over a 2 week trip, and using a 'real' 4x4 vehicle, it actually works out cheaper to bring your own vehicle across from the UK or continental Europe than flying in and renting. This assumes of course that you have a 4x4 or a 2 wheel drive car that you don't mind getting trashed - the best locations are a good vehicle trashing drive to get to.
As far as the X-ray scanning goes, I asked the staff at Heathrow if I could take the film through as carry on and they said no, but assured me the checked-in scanners were no worse than the hand baggage scanners and would not cause a problem with one scan. I don't believe them but as I brought the film back again I will put a roll through the camera to see what effect it has had. In the hope of minimising mechanical handling and shocks I took the 'Peli Case' containing my cameras to the oversize baggage check in. This experience then confirmed my pesimistic view that using a lead bag just results in the operators turning up X-rays to eleven until they can see inside it. My medium format camera is a Horseman 980 technical camera, which when folded up is basically a solid block of aluminium. Because the operator could only see a dark square blob they put it through the scanner three times (probably increasing the power each time) before giving up and asking me to open the box for a hand search. The film was in my rucksack which hopefully only got one standard dose at the end of the check in conveyor belt.
Incidently, last year I went on a short duration 'round the world' trip and a couple of rolls of 35mm Velvia 50 I had must have gone through 10-12 hand baggage scanners with no visible ill effects.
On the way back the only restrictions for carry on luggage was taking liquids through the security check, and I think things are a lot less restrictive at Heathrow now.
I think that's everything covered.
Crispin