The problem with the map border is that hitching posts near the border can lead to the leashed animals wandering onto another minimap, should that area then be unloaded they'll be un-tied (as of the hitching post not being on their minimap) and despawn. As the OP didn't post a minimap shot... can't be sure if that's the problem.
Other option is someone messed with them somehow that lead to them being un-tied (which leads to despawn on area unload).