IIRC, the icelandic banks are covered by their own guarantee scheme, which is similar to the FSA one. Same goes for Irish banks. Although some of them are set up so that they offer accounts to UK people under a UK-registered offshoot, which is covered by the FSA £35k rule.
edited to add: I think it's the FSCS, not the FSA. See www.fscs.org.uk
Yep - made sure the banks I chose are covered by the FSCS scheme and its £35K guarantee. In fact, one of the criteria for a bank to be mentioned here is that your saving must be covered by the Financial Services Compensation Scheme.