I believe you can do it if the guard at the entrance of Midgar begins wondering where he left the key, then he says that he "might of left it in the excavation site" if he says that, then you're good to go. Remember to dig at the top part of the site, right near the tent (or is that the harp...?)