It is/was legal on rural interstates in Washington. I've cycled down I90 in roughly the North Bend area (in the late 90's).