My understanding is that in Iceland it is illegal to do this because BTC is treated as a foreign currency, however it is really not clear. And I think I can directly make purchases with BTC but there are very few options.
Isn't it a capital control thing? If you're bringing in currency to trade for the local one then that's no skin off anyone's nose.
There is an Icelandic localbitcoins page, albeit not exactly buzzing. That should be enough of a sign that it's not outlawed or at least tolerated.