If the airline you select will permit open jaw award travel, you might try flying into Anchorage, seeing what you want to see, then taking the train north to Fairbanks, seeing what they have, and departing from there. Open-jaw travel lets you see more places for the same number of FF miles. AA permits open jaw, but I don't know about the other carriers.
I've had no difficulty booking AA (and AS) award travel to ANC and to FAI...in fact, I'm headed back to FAI next month.
Edited to add this link to a rumor about DL pulling out of ANC:
http://www.flyertalk.com/forum/Forum21/HTML/008968.html
[This message has been edited by Middle_Seat (edited 01-20-2003).]