Maybe try waiting? That's what I do when I lose a follower, but don't know if it'll work for a horse though. I'd just give up on him. Horses do odd things in this game. They are prone to dying in weird/funny/tragic ways, getting lost, and picking fights with things that can kill them.
IMO, horses are a 1000 septim way to get a laugh.