I have never heard of said "Magic Counter" materia. There is a Counter Attack, which is a purple Independent materia, and then there is Counter, which is a blue Support materia. I believe this is what you're talking about. And Zeromus is right. There is a Counter materia in that room. If memory serves he is correct in it's position in that room as well. Check again. You find Mega All in a different part of Northern Cave than Counter.