First of all, if the players are allowed to use a resource, of course you should use it too where it's appropreate. That includes not letting every enemy use it to prove a point. Use it once or twice with an enemy caster to shut someone down, the players should have resources to recover from ability damage by the point they can cast 3rd level spells. You could, as you have already done, take the last way out and admit you made a mistake to allow that spell and ask the player not to use it in order to let the other players feel useful too. From what you describe, either you made a bad argument, or your player is the kind of person you should neither befriend nor play with. That being said, I would rather strive to mitigate the impact that single spell seems to have on your campaign than to force some kind of conflict with the player using a resource you clearly have given him as a valid choice.
You could just include an opponent or two immune to ability damage. Or make half of your arsenal immune, like running an undead -heavy lineup, or using a lot of constructs, both types making for good minions to a caster of any kind. A swarm or two here and there could work as well. A few undead-esque prestige classes grant immunities too. It's good to remember that creatures of the cold subtype are immune to the damage as well, so... if the player likes Frostburn material so much, why not pull a Frostburn type of adventure?
Or, for that matter, go the other route and give the enemies a cleric once in a while that can protect/save them from Dex-based paralysis. Even a low-level minion with a wand or scroll of (lesser) restoration can mitigate some of the potential harm from that spell. A foe with feats or prestige classes to combat undead (a vengeful inquisitor that believes the PC's are affiliated with undead in any way, for example... correlation is easy to establish) may have defenses against ability damage. Casters get some ways to avoid taking evil stat reductions too, and there are always magic items (as well as Naberius and the Strongheart Vest).
How is the melee touch attack (often a bitter enemy to squishy casters, the archivists being no different) being delivered? Spectral hand? That's another spell with short duration sacrificed for the combo, and it can be easily dispatched with area damage (casters usually don't have good Ref saves, so the Improved Evasion doesn't do much to protect it) or a well-placed attack (with ghost touch, a truedeath crystal, or a serren weaon, or just gamble with a magical one... this technique gets moer reasonable with multiple enemies). If reach spell or similar techniques (smiting spell, spell storing) are used, it's another heap of resources spent (unless the player has Arcane Thesis (Shivering Touch), which would be a serious slap in your face, or similar measures). If channeled through an ordinary melee attack in some way, hitting becomes even more of an issue.
The enemy could up it's defenses against attacks in general or touch attacks in particular, too. That dragon with low Dex and touch AC? Bam, Scintillating Scales. That spellcaster that looks like it took Dex as a dump stat? Mirror image, blur, displacement, blink... heck, even (greater) invisibility. You can't attack what you can't find. Snipers are another take on that strategy. Other enemies already have good touch AC... stealthies, many casters, a lot of outsiders and fey...
My last suggestion would be multiple enemies of similar strength instead of just one single low-Dex target that can be instagibbed. That would lessen the impact considerably. Or even mass assault the players with a lot of weak targets. So what if you can Shivering Touch an enemy into paralysis when the melee guys kill multiple enemies per turn or an AoE spell levels waves of enemies?
A lot of these suggestions are pointless if you are running a premade adventure or have already planned your entire campaign and are allergic to changing details here and there, but for the most part, know that there are very few abilities out there that are just that good without having a reasonable counter to them, especially for an enemy that does his research (divinations, espionage, knowledge/gather info).
