Cameras are probably the best anti-theft deterrent I can think of. I have had to use them in the past on several occasions to find the lunch thief. They obviously need to be pointing correctly.
How I plan on handling keeping food out of lockers? A sign stating: "Absolutely no food to be stored in lockers," discussing it at monthly training (these were already implemented by previous director), company issued locks for all lockers (even the ones not claimed, otherwise you will find people claim them as temporary food spots).
To handle verification: monthly spot checks (part of the GMP check for that area now), and probably an annual full locker check. I've got HR going with me for the locker checks just to assuage any possible fears of privacy breach.
I still personally think it's overkill not to allow food in lockers in the lunchroom, but smarter people than me from this site have helped me see it's still something I should be doing.