[Bloodstalker]

Evil characters won't leave you party if you are IN TOB, but even with TOB installed, if you are still in the SoA portion of the game, they can leave you.

As far as Nalia goes, if you have the keep, I believe you can still dump her and keep it. Imoens level will be somewhat higher than it was when she was taken from you, but I am not real sure how that works out as far as knowing the actual level she will be. Her thief skills are better than Nalia's I think, but honestly, I have never seen much difference between the two myself. I always take Imoen in the party, but that is personal preference. However.....
Spoiler.
.
.
.
.
...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
If you have a full party when you pick up Imoen, whoever you leave in Spellhold is there for the rest of the game. You can't get them back, as they stay there.