I've struggled with this, and I can tell you a few things that it is NOT, and a few things that will cause this every time.
Carnivores and Bone Eaters - Unless given [NO_EAT][NO_DRINK], these guys will starve as a race, every time. Giving them animals to eat does nothing to stop their deaths, as butchery doesn't seem to happen in world-gen
Cave Dwellers - If an entity race lives in a cave, they will starve to death. Any race that likes dwelling in caves, and has creatures move there, will have those creatures starve, guaranteed. Something about caves and the game not giving them foodstuffs or the ability to farm.
Dark Fortresseers - The Above goes for Dark Fortress races, as well. (Although they seem to be able to get some food from indoor farming)
Farming - Farms only work for Mountain Homes or Cities. To a degree, outdoor farming works for Forest Retreats, but the yield is much lower. Not everyone will starve in a Forest Retreat, but they cannot have high populations without death.
Trading - Food will be traded back and forth between connected cities. If all the food in a region is gone, it seems the TOWN they are connected to starves as they sell all the food they can get, while the farming hamlets eek out a subsistence farming living.
Overall - These problems are occuring because Toady implemented worldgen starvation without completing the caravan arc. It's being worked on now, but we're only in Release 1 of the Caravan Arc. Once it's farther along, goods distribution and usage of available resources should be much better. Be patient, grasshoppah.