I believe I found a "bug". I'm in Sand Dragon right now and I have been unable to find either the red or green key... I've unlocked 10 of 12 secrets so far without getting behind either the red or green doors.
Any way you can guarantee that the keys will always be available in the area you can get to? I'd also recommend not putting them in secret(s) either.