Uuuhm, I don't remember where but you can buy magic keys from one of the villages on the floating continent/whatever.
This site is where I usually go for gaming issues. Also, never use the fat chocobo.. there's no point putting your items there.
What's your party like? xD