I'm going to third the little Mandrags. I love plugging those little things, I'll like it even more with the PLD sleep resist.
You know, the key quest isn't hard, just time consuming. If you don't have friends or guild mates that can help you, just Head to the various zones and hook up with the 20-30s that are looking for keys. Explain to them that it "goes faster when we work together."
(BTW, we set some kind of record for getting keys in P-Mines, 2 WARs and a WHM, we got 3 keys in less than 15 minutes!)