Though the guru says 'it hasn't been available for a long time' he aslo says 'it was used as money'. I'm guessing there was a fair bit of it around in Zeal for it to be used as currency, and the reason it's unavailable is that it's all at the bottom of the ocean in the time periods that follow.
Why not get more in other time periods? The technology wouldn't be available in earlier times, and in later times it may well be the Zeal race had mined most of it out already, and perhaps also the technique for mining and knowledge of where it was found are lost.
Taking this theory in a craaazy tangent...maybe when the red rock hit the ocean floor (the closest place to the core of the planet) it was re-absorbed by Lavos? That would certainly make it so that red rock was not available in other times...Yeah, odd theory, not sure it that one even makes sense.
But I think in Zeal it wouldn't be impossible to have a golem made from Red Rock.