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.
Doing some quick testing, I've found that you can teleport players that are riding something (horse, minecart, boat, or pig), although that may be due to the fact I'm using the latest snapshot. However, whatever those players are riding will not be teleported. That means that the poor owner of the horse will be back in town while his horse is left to wander the wilderness alone. A horse owner might not be too pleased at that. The solution is to first teleport players riding horses into a secure corral in town with the following command:
/execute @a ~ ~ ~ tp @e[type=EntityHorse,r=1] <x> <y> <z>
and then to teleport everyone to the meeting place with a standard teleport command.
For some clarification, this is what the above command does: at the location of every player, execute a teleport, filtering on horses that are within 1 block of a player, to the coordinates <x> <y> <z>.
As I said, this is tested on the latest snapshot (14w20b), and so may not work as expected with earlier versions.
Best Answer
Horse armor doesn't have durability, it'll only be removed from the horse if you equip different armor on the horse. As such it is not repairable. I do not know if it can be enchanted however.
Source: Minecraft Wiki