IIRC this is the way it should work:
If you have no chocobo lure the battles will be selected from the region's encounter table. AFAIK, these specifically omit the chocobo formations. I could be wrong on that.
If you have a lure, there is up to a 85 percent chance (or something high like that) that the battle will be chosen from an entirely different encounter table that only contains chocobo encounters for that region if there are any. I believe the information on which zone you're in is determined by the walkmesh of the world map.
So you shouldn't be getting chocobo encounters without the lure.