As the title says, Frost is my horse, and while I was out adventuring, I jumped on a random horse. (Frost likes to wonder off and leave me stranded) When I fast traveled back to town, that new horse was next to me, and Frost was gone. I can't find him anywhere? Anyone know how to get him back? (Xbox 360)

Riding on a different horse will make that horse the one you own. What happens to your previous horse I do not know. Suggest you load a previous save if possible.

My last save that I can find Frost in, is from 10 hours of game play and quite a few quests ago...

Maybe look in the Black-Briar Lodge, where you first aquired him? Or in another stable.

It may take 72 game hours for the horse to start making it's way back to home base, then the amount of time it takes it make the journey.

Check the lodge and the Riften Stables in 5 game days. Not sure where his home base is, also, to that end, check the Whiterun stables as that is where I saw Lachance after this quest.

Thanks CCNA, I'll give this a try.

My frost disappeared 50h ago in game too. Figured he would re-appear soonner or later but never did all I can think of is that he died

Oh, so if I'm sick of that horse I picked up at the Fort (which is lovely, nice, helpful and everything, but wanders back to the Fort every time we reach our destination, only to magically appear every time I fast travel to a new destination), all I have to do is formally buy my own horse, hop on it, and the old loyal horse will just wander back to his old Fort permanently and be safe there?

Will that also work if I got Dawnguard and rode the summoned horse?

If by summoned horse, you mean Arvark, then no, he just de-spawns after you get off him. And you can re summon him at will. Pretty much the best horse in the game. He can't die, and is only around when you need him.

*chuckles* Which Lachance? That one? Or that one.. or that one... or that one... or that one?