^If you look over the whole history of ST, there's plenty of evidence that cloaking devices aren't a single technology, but a succession of different technologies that get penetrated and then replaced by new stealth systems in an ongoing arms race between concealment and detection. Consider: In "Balance of Terror," the Romulans' cloak rendered them invisible to optical detection, but their ships still registered on motion sensors; yet by "The Enterprise Incident," that problem had been solved and the ships were totally undetectable. By ST III, Klingon cloaks were detectable by a visual distortion, and had to be dropped before a ship could fire; yet by ST VI the Klingons invented a new type of cloak that had no visual distortion and that could be kept up while firing. And Spock figured out how to penetrate that type of cloak. Yet by TNG, over 70 years later, cloaking technology is impenetrable again and ships do still need to decloak in order to fire.
So canon already gave us several cycles of different cloaking technologies being rendered obsolete and supplanted by new ones long before ENT came along. Therefore, ENT's 22nd-century version of cloaking is not a mystery or a paradox at all; it fits in just fine with all the other forms of cloaking that have been developed, penetrated, and discarded.