Where is my horse?

The horse definitely wasn't killed by monsters, but it died nonetheless.

Using NBT Explorer I opened the world save, navigated to the region NBT branch, and ran a search for the horse's owner's name. Since horse entities are stored inside the chunk data inside regions and have an OwnerName NBT entry that contains the name of the player who tamed them, after a while this gave me a complete list of all living horses tamed by that player. The horse in question ("Giblet") was not among them.

The horse probably drowned under a jungle bush's leaf block while having a swim, or fell off a cliff. Now we know!

Had the horse been alive, this method of digging through the region data with an NBT editor/reader would have worked quite well (and did, for all our living horses). With access to the save files, this is the most direct and non-invasive way to locate a horse lost under a wide variety of circumstances.

Horse Locator Mod

You can use the horse locator mod. It shows you the coordinates (and the relative distance) of the nearest horse to your current position.

It is compatible with Forge and SMP. I used the mod in 1.6.1 but it should work in 1.6.2 as well.