I like the cicadas' solution by Wrzlprmft.
The basic idea is to genetically alter cicadas into breeds whose adults emerge at regular time intervals that match up all breeds after 500 years.
That idea is brilliant, but I thought up some detail improvements:
* How to keep people from seeing cicadas as threat? - Tell them the cicadas aren't eating the food for themselves but bringing it to the promised land. That's also perfect reasoning, why food storage is disallowed: The cicadas can't bring it to promised land, if you do. You'll be stealing it from your ancestors and your future self, if you stop them taking it.
* How to control the numbers of cicadas so people really don't notice? - Have a predator that only eats adult cicadas and other insects. The predators will have a steady supply of cicadas as the breeds don't align. The steady supply will keep the predator population increasing slowly together with the perceived growth of cicada populations. Without the predators the cicada populations would actually grow exponentially.
* How to get rid of the predators before ultimate doomsday? - Note that the maximum distance between two populations is (shortest breed) years. This maximum distance will actually occur right before doomsday. Plus, there are (number of breeds) populations that are close together before doomsday, i.e. 20 years vs. 1 year between 479 (21-year brood in t-1) and 480 (20-year brood in t-1). The closely aligned populations will cause an increase in predator population. This will mask the exponential growth of cicada population. In the next 20 years the predators will starve.
* How to make sure you get rid of predators for doomsday? Tell your believers to watch out for the rapid growth in predator population. Instruct them to root out the predators, if that happens. Also instruct them, to wait as long as possible, because they will trigger a war of cicadas vs. 335
predators and the promised land needs to be prepared for this war. About 15 years into the war many cicadas will come and so will you to take your people to promised land on the back of giant cicadas.
* Why that part with 15 years? Your people will be waiting as long as 20 years for the cicadas to come. If you don't predict a time (and anything fails) they fall from belief too early. After all an important thing of their cult is missing for one of their own generations. If they do after 14 years of waiting, you'll be in a pinch. After 15 years you'll still be safe. However if you say 20 their faith might be strengthened by the perfect match in your prophecy. Even if they start wondering after 15 years, they'll only be devastated when after 5 more years everything blows over with no (promised) land in sight.
* Wait, how long does it take to fall from belief? Start at least one year early. Your people will lose all their food during summer, when the cicadas come. Even with most of the food gone they will survive for some time from roots and stuff the cicadas didn't eat. Most of them will starve at the end of next winter, when really every bit is gone and nothing has grown back yet. That's about half a year. Give them some time to get desperate enough to fall from belief. Plus, there are 20 years to come with no cicada fetching food or carrying them to promised land. Let that add to the desperation, if doomsday didn't work out. You got still 5+x years left of safety to observe and find a way to cheat, if needed. 121