Since the 1.7.0-update, when putting a lead onto a HORSE, the horse is not held by the lead – if I go away (or the horse does), the lead stretches and comes off. This effect is the same, regardless of holding the lead in the hand, or fixing it to a fence – the horse will soon get loose.

UPDATE: found out, this issu only applies to 'OLDER' horses, tamed a longer time/several Minecraft-versions ago, recently tamed horses can be leashed normally.