I think spell components or other resource limits could work (didn't a cast of stoneskin cost like 250gp once?) However, most RPGs suffer from massive loot gloat to leave your player swimming in resources after a while. Fix that too and you'll be in business.
This 'hidden, randomized cooldown' idea strikes me as really good. You could even keep the currently imba powers of most magic systems so long as you made the cooldown steep enough. Mages could blast away and be generally demigodlike, but with the nagging fear that doing so too much risks doom and bad things. It also forces more canny play if you simply do not know how many spells you 'get'. In short, magic becomes a weapon used only if you're in real trouble. It also makes it more scaleable - instead of 'well I get three magic missiles a day', it is more 'I would rather not use any spells, but if I am really in trouble I can shoot off as many as I need - albeit with increasing risk of catastrophic failure.
A related idea is having some general measure of how many spells you have ever cast, with some set of adverse or otherwise effects at certain thresholds (bit like the MOTB mechanic). Lots of settings have elderly mages going crazy or evil or whatever, and adding this worry to the player acts to further balance them.
Of course, you could combo all three. Keep magic at its usual imba self, but make it very expensive, with hidden cooldowns tied to adverse effects to discourage too big a gorge of spell slinging, as well as a general counter of magic use, also tied to adverse effects, to again encourage magic to be used sparingly. If I ever play D&D again, I'll definitely use that.
More direct feedback (e.g. adverse consequences like perils of the warp etc.) are not such a good idea, as in computer games you'll just reload.
Maybe there is a general principle here. Players tend to be uncertainty-adverse. Thus forcing uncertainty can balance options that would, in principle, be OP.