RP, you may have found these already, but just in case here's links to online bicycle maps for Washington/Oregon/Montana/Idaho, that may help with route planning:
Oregon & Washington:
http://www.portlandonline.com/transp...x.cfm?c=34809&
Montana:
http://www.mdt.mt.gov/travinfo/maps/
Idaho:
http://gis.itd.idaho.gov/bikemap/
There's paved rail/trails called the Centennial Trail / Trail of the Couer D'Alenes)
http://friendsofcdatrails.org/CdA_Trail/index.html
they run pretty much the whole way from Spokane to the Montana border, so that might make for an interesting route. Have heard good things about them.