Long time ago, I kayaked from Shiprock to Bluff. Took two long days. Lots of Russian Olive and lots of dead cows hanging in the branches. One rock dam in the upper section that I looked at before running. Country seemed to open up by four corners. Remote, no people, definitely worth doing at least once, if you're into that sort of thing. Would I do it again - sure, why not.
Montezuma Creek to Sand Island is an easy one-day and a nice two-day trip.
My understanding of the river above Shiprock is that there are lots of diversions and fences. Doesn't sound worth the trouble.