All Icelandics have to be microchipped to be registered, so all our foals are done at weaning. We've been doing them for more than 20 years and have never had any problems with chips moving or failing, but I wouldn't use it as a theft deterrent as it's not visible to a potential thief, and certainly abattoirs and markets don't routinely scan horses (and of course for a private sale it's not expected anyway).
Purely as an deterrent I would choose freeze branding - it's highly visible, relatively cheap, and not too painful for the horse, and it doesn't grow out like hoof branding. Also nowhere near as painful and stressful as hot branding.
Mic