If I recall correctly (Please forgive me, I haven't played in some time), Companions always appear in your castle when you go to your hall regardless of where they currently are on the map, and whether you've recruited them or not. You need to find the castle they're captive at and rescue them from there to free them, either by doing the sneak in thing, or by taking the castle.