IS delegation requirements are as follows:Nameservers must allow connection to UDP port 53, and to TCP port 53 as well.
SOA records must be correctly formatted:
Master nameserver correctly named in the MNAME field.
Working mailbox of responsible party in RNAME field.
Times (refresh, retry and expire) according to RFC1912
TTL for NS records not lower than 24 hours.
Correct NS records. Properly registered in the appropriate zones, both forward and reverse. I.e. the nameserver's name must be included in the PTR record set for the nameserver's IP address.
After 4 days of fruitless emails between me and my ISP, here is the latest:
<admin note: email text paraphrased [webmasterworld.com]>
Our nameservers don't allow Zone Transfers on TCP Port 53 to avoid a potential exploit due to a vulnerability in the Zone Transfer process. Our firewall denies IP packets for TCP port 53 to prevent unauthorized zone transfers (...) our nameservers do not respond on port 53. AFNIC's rules are not compatible with our system.
[edited by: encyclo at 1:12 am (utc) on July 7, 2009]
It is not unreasonable for your host to disallow connections that they feel pose a security risk to their systems. However, the requirements of the .IS registry are unlikely to be changed to accommodate your host. Your host is being a bit obtuse in referring to AFNIC's (the .fr registry) rules and not those of the .IS registry, but effectively the rules are similar so the situation is the same - stalemate.
This doesn't mean you can't purchase and use your .IS domain with your current hosting company - just that they are not prepared to meet the .IS technical requirements, and as such they can't host the DNS. The can still host the site itself, however.
This leave you two options: the first is to see if your .IS domain registrar can host the DNS for you (many do offer this service, sometimes included in the domain price, sometimes at additional cost). In this case, you set the nameservers to those of the registrar, and you edit the zone file at the registrar to add the appropriate A and CNAME records. Your host will tell you what settings to add. I'm not familiar with the .IS ccTLD so I don't know the relation (if any) between the registry and independent registrars though, so this may not be possible.
Your second option is to purchase separate DNS hosting from a third-party provider. In both of these cases, make sure that your host will inform you in advance of any change to your hosting plan such as a change of shared or dedicated IP address so you can make the appropriate modifications. Good luck :)