Actually, if you go with the ruling that the Nazgul doesn't still need to be in play, then... why did there ever need to be a Nazgul in play in the first place? If you go with this ruling, you could theoretically put
Return to its Master into a deck that doesn't even have any Nazgul, and it would be playable (so long as the Ring-bearer is wearing the Ring, of course).
As far as my opinion goes, I don't see why you can't play the card without a Nazgul in play. After all, doesn't the comprehensive rulebook say something about "completing as much of the effect as possible"? You can't assign a Nazgul, but you can sure cancel all remaining assignments!