The rules do not seem to explicitly spell out the answer to this. We see this happen sometimes. Until someone has authority to make an official ruling and keep the Current Rulings Document up to date (which will be so nice someday), we will just interpret the best we can with the related rules that we have.
In this case, with
Ulaire Nertea, Dark Horseman, the card says the Free People's player cannot assign him to Gandalf.
So what this really comes down to is: Does preventing the Free People's player from "assigning someone to skirmish..." also prevent them from "replacing someone else in a skirmish involving..."?
I would say "Yes", because I interpret that "may not be assigned to skirmish...by the Free Peoples player" really means is that "the Free Peoples player may not choose to put that specific minion and that specific Free People's character in the same skirmish".
With that interpretation, it would follow that the Free People's player may not assign Gandalf to skirmish
Ulaire Nertea, Dark Horseman, nor have Gandalf replace the other companion in a skirmish involving
Ulaire Nertea, Dark Horseman. It would also follow that
Pippin, Brave Decoy does not get around
Shelob, Her Ladyship, since he is prevented from skirmishing any minion by either player.