If you could install three or four devices per stall, on each wall and possibly door, you could halve the distance requirement to 50 cm, therefore making it 8x easier to detect. This could make design so much easier and lower cost that having multiple units wouldn't be a problem. You can design it to the size of a coin cell!
In addition to the point about false positives made by tggzzz, remember that people also will be pissed off from false alarms, and for a good reason. And it is almost guaranteed that most employees won't handle these cases as they should because they are often already stressed from shoplifting, and the principle of presumption of innocence is not stressed enough. So, really try to avoid false positives. I'd say, if more than 5% of alarms are false, forget about it.
How do you plan on handling the situation of someone having very weak magnet, heck, even some magnetized metal, who happens to put it near the detector? If you need to detect a strong magnet @ 50 cm, you'll detect almost anything @ 5 cm. You could add some proximity sensor that would lower the detection level, but it will get very complicated soon.