The first time I played, I killed Lost Number, grabbed the Materia that pops out, and left. I didn't realize the key was there until I was exploring the area again like 20 play hours later (fortunately I was still on Disc 1). I felt kind of silly. But I have always gotten both characters.