Velax said:
http://forums.taleworlds.com/index.php/topic,135014.msg3254306.html#msg3254306
But I think this is a problem that wasn't covered by those threads yet.
Phienyx, are you sure the companion status report says nothing at all about their wereabouts? Make sure you checked the the companion missions report page under "reports" not just in the character pages.
There should be something like "trying to rejoin party".
If the companion missions report doesn't even list them, they might simply no longer be your companions and have left your party without speaking to you first. That's not a nice behaviour but on the other hand rotting inside a dungeon and not being freed or ransomed isn't funny either.
However, they might show up in any tavern as soon as your renown reaches a certain value. Yet there might be a bug and they are lost.
If you are quite curios and consider cheating (just to check out if it's really a bug) you could rise your renown artificially with the cheatmenu and check the taverns. In any case I'd like to know whether you get them back or not so please let me know what you find out. (You can also send me a PM and I might check a savegame for you.)