There are three regional search engines in Iceland
leit.is (Home Made / no www)
finna.is (Home Made /Google for www through XML)
Embla (Home Made / No www)
Then there is Google and Ha.is (the fourth local one, mostly used my the Univeristy of Iceland)
As for Directory Search or Yellow Pages, there are
Iceland Export Directory
www.randburg.com
gulalinan.is
gulasidur.is
export.is
thats about it for Iceland.