And it goes poof!
 

It seems that on occasion, when you get off of your horse, it just disappears. I've lost three horses to this, and others have lost some too.

Perhaps this is a way to control the horse population, but that's unfair.

That happened to me too. It's not gone, it's just somewhere on the map. Mine was in really deep water and I had to make a boat just to get it out :|

It usually will appear where you mounted it, or somewhere along where you'd recently ridden it ..

.. I recommend backtracking before losing hope.

Another tip, which I believe helps .. wait a moment before dismounting. Just let the server catch up and realize you're not moving anymore.

Some of mine turned up at the last restart point - docks, most of the time, be it what I disembarked there or just passed them and saved there.