I 'lost' a companion and they eventually turned up about 2 weeks later! I think the companion will keep trying to return to you but they are limited to using the regular paths and roads, whilst you can use shortcuts and 'fast travel'.
What is annoying is forgetting where you left your horse. They stay more or less where you left them. That's fine if you left them in a town/village, but leave them out in the open and all you'll find is a pile of bones, because wolves have eaten them.