[spoilers]After you invade Midgar on disc2, there'll be a guy waiting outside one of the sectors. After you talk to him, a Key to Sector 5 can be found in Bone Village too, and you can get back into Midgar from the church up to Wall Market.
Well, I'm not exactly sure when the guy shows up out there, but I think you do have to talk to him first.[/spoilers]