SAS is doing a three class service to KEF from OSL with good connections from LHR, AMS and FRA if you would like to travel UA from the states. Award availability is pretty decent on SAS these days (SAS have revamped the internal system thus making the operating entities more willing to open up award seats). Remember that SAS has three award buckets; the usual *A-aligned X and I plus itīs own P for Economy Extra which usually has the best availability.
For domestic flights in Iceland you need to buy regular tickets I am afraid.