that might be it... I'm almost always at capacity, but I will say I have had companions come back successfully and then found I was over capacity and had to dismiss some recruits, and was still able to access my companion. I think maybe you also have to have all companion slots filled, and / or possibly also all prisoner slots filled as well? I haven't been able to test which combination of factors does it vs which doesn't because I always miss this happening until several in-game days have passed and by then I don't have a before / after save to play with.
As of 1.3 beta though, now this seems to be getting compounded further in that some of my companions that return from missions will appear in my party, but I won't be able to access them in the inventory screen. I think the same dismiss/rehire workaround should still fix it (though I rage quit so I haven't been able to test yet). I'm not sure if its related or not, but the circumstances seem quite similar.