Very interesting discussion, and I'd be interested Granty to hear what you ended up choosing to do.
I'm also in the process of selecting how to get my images printed, and it depends on the market I'm selling to. Up till now, for weddings and portraiture, I've used DS Colour Labs who use Fuji Professional Paper and Fuji Frontier Printers. There's no data on how archival these products are, I haven't even been able to find out if the paper is acid free (this is what some pros use as the definition of archival, given there's no actual standard), although I have emailed Fuji to ask about their paper. I suspect these are not their best papers, since they do have a specific archival range, see
http://fujifilm.co.uk/professional/prolabs/main/fujicolorcrystalarchivepromp.html
These archival papers are reviewed here:
http://www.wilhelm-research.com/ist/WIR_IST_2007_03_HW.pdf
They are given 40 years under normal glass (i.e. not special UV resistant glass, which gives jsut 10 years more). So how long would the normal Fuji Papers last, i.e. not the Archival ones? Who knows? But I do know they are widely used, including by Photobox as well, who are a cheap mass-market online photo company. A few years back I took one of their photos, covered half of it, and left it on a windowsill in direct sunlight (except there was double glazed glass between the sun and the image). There was no fading over the 4-6 months I left it there, which is impressive. So if you take that paper and frame it behind glass as well, and hang it on a wall in your house where it's not exposed to a lot of direct sunlight (i.e. probably almost any wall), then there's a lot of protection from UV (which appears to be what does the damage). So to summarise, the standard (non-Archival) Professional Fuji paper used by DS COlour Labs and Photobox are probably going to be fantastic for decades.
But, I've also started doing 'fine art' landscape prints, and people's expectations may be higher in this market. So I have researched where I can get better prints. According to the Wilhelm Research Paper, certain HP printers and ink are best (life of more than 200 years behind glass befor enoticeable fading occurs), but I can't find an online professional printer offering these. If anyone knows of one please post it here.
The best I can find are the ones that use Fuji Archival paper. DS Colour Labs use this but only for Pearl prints (which only works well with B&W and saturated-colour prints), and they are very reasonable as usual. Peak Imaging are more expensive but offer a much wider range of Fuji Archival papers - I will email DS Colour Labs to see if they will increase their range too. Loxley Colour also use the Fuji Archival papers, and are also expensive.
So to summarise this bit, there are some options for Archival Papers which some people out there may wish to consider.
As far as giclee prints go, it feels to me more like a fashionable word than a marker of actual quality.