I would like to say hello to everyone as I registered just recently, but for more than 2 years I've been reading the BPL forum a lot ;)
Great photos indeed!
However, in my opinion you guys simply took too much gear for your trip and did not plan it properly. Here are some points:
1. In 2009 I made solo East-West traverse based on A. Skurka's and Olivier "Rando léger"s descriptions. My route was: 980 road/Geldingafellskali/Karahnjukar/Alftadalur/F910/Askja/Nyidalur/F26/Versalir/Hald/Klettur/Helgaskali/Hloduvellir/Botnsvogur.
2. The trip took 16 days during which I covered ~460 km by foot. The weight of the pack was around 20 kg (though I had non-UL equipment/food - I was simply too poor to buy high-tech gear/dehydrated food etc.).
3. My friend Piotr (first UL person I got to know) have seen you and Chris when you were on your way from Akureyri to Nyidalur (and also in the camp) so I also know his first-hand impressions;)
4. Last month (July/August 2011) together with Piotr and my girlfriend Luiza we went on 16 day trip on Hardangervidda, Noway - hiking and packrafting UL style. The weight of both packs - Piotr's and mine - was around 20 kg each (with whole camping/packrafting gear, clothing and mine with DSLR - Canon EOS 7D with two lenses Sigma EX 10-20 and Canon 50mm). Luiza's pack was around 13 kg (with clothing, packraft, food etc.)
And here what comes:
1. "However, it was backpacking as light as was possible."
Check - sendspace.com/file/9azzfc - here you can find my gearlist for 2011 - hiking/packrafting (glacier equipment would add no more than 2/2,5 kg).
(i) actually I took a bit less
(ii) it could have been a bit lighter.
I bet a lot of people on BPL would prepare even better (read: lighter/more effective) gearlist.
Most of the things you took could have been much lighter, but still enough for hiking through Iceland - starting with shelter, sleeping bags, clothing, stove, trainers instead of boots and ending with compass and other small stuff.
2. You do not need to plan the 250k trip for 25 days with 40 kg of gear (compare this to Andrew's or Oliver's trips or even my 460 km/16 days (with 5 days of rest)/20 kg).
This is true especially when you are walking through a flat/rolling surface like Iceland. There are only two problems there - rivers (which mostly can be crossed/packrafted) and weather (you simply need to get used to it).
Right now I think that you can plan trip like the one you had for no more than 8-10 days of really easy walking. And if you are at least bit fit and the conditions are quite ok - less than 5 days.
3. Having read your articles, seen photos, watched movies and heard what Piotr told me - I can tell that you were not prepared both:
(i) physically (carrying 40 kg around twice as slow as he and his companion - Valdek - and they are not some hardcore ultramarathoners), and
(ii) in terms of logistics (not enough food/calories; too much gear/bad gear choices - taking a TOO MUCH of very light gear instead of taking ENOUGH of very light gear).
4. I also met people who made wrong choices in 2009 - two guys from France who read Oliver's article and decided to traverse Iceland. They had no previous experience, they were not fit and bought light packs (Golite Pinnacle) but took traditional gear - tent, boots etc. They finished their trip in Askja because of leg injuries.
5. I guess that you trapped yourself also with food: long trip --> more food --> heavier pack --> slower pace --> more days needed to cover the distance --> need more food.
6. "We had a map, the best I could find anywhere. It was from the 1930s."
I'm not sure but you can buy the map of every place on Iceland in 1:50 000 scale (dating 1988-1990 http://www.ferdakort.is/images/stories/yfirlitskort/50-000.gif) + CD Maps from Ferdakort + download very good, free GPS map from Dieter Graser's website isafold.de.
7. "We didn't try to fish but we should have done (although it was illegal)"
Fishing on Iceland is not illegal you just need to buy proper permit.
8. It's hard to call it expedition. There are a few companies offering different traverses - north-south, east-west etc. Prices starting from £2000/€3500 and a lot of independent people who completed various routes through Iceland - solo and unsupported.
PS. Oliver utilized front pouch during his trip and as his report indicates - it worked very well.
"Another idea would be to burn wood. It looks like you spent quite a bit of time in areas where there wasn't any fuel though. If you did spend time in places where natural fuel was plentiful than planning to build a fire might be a good fuel-saving strategy. Perhaps even carrying a small wood-burning stove as well as the other stove."
There is almost no wood on Iceland - mostly volcanic ash, sand and lots of Reindeer lichen etc. Generally speaking - very little vegetation (and it is protected). Alcohol/gas cartridge/kerosene - these work better on Iceland.