I have various bone village troubles as well. I can't get much at all. Refresh my memory. What type of treasure do you search for to get the key?

Also, if you really want to finish off big materia, such as KoTR and all the blue materia, Just Beat Emerald with the Apocolypse. It does less damage when you attack, but miming KoTR works better anyway. 150,000 AP isn't half bad, you know?