I know this'll probably invite scorn, but Icelandair actually has its own FF program, SagaBonus, so you can join that and earn 100% miles. Granted, the miles will only be useable on Icelandair, but they're still miles and it's still 100%.

They used to be partnered with SAS but that ended April this year. Currently they're only partnered with other Icelandic airlines, car rentals and hotels. I suspect they're looking for new partners, but who knows when/if that'll happen.