^The simple fact is, cloaks wouldn't work on most Starfleet ships. The more power a ship puts out, the more powerful the cloak needs to be to conceal it, so there's a point of diminishing returns. Cloaks are only practical on ships that keep their power use to a strict minimum: stripped-down, no-frills warships. No holodecks, no science labs, no arboretums, not a single luxury. So a ship like the Enterprise
or the Titan
couldn't practically use a cloak anyway. If you ask me, that's the real reason the Federation agreed not to develop cloaking tech.
What I've always had trouble believing is that the Klingons would use cloaks. I mean, if Starfleet wouldn't "skulk around," why would the Klingons? Wouldn't they consider it dishonorable to sneak around and hide? Sure, you can somewhat rationalize it on the grounds that warriors value stealth, and that you have to decloak to fire so you're still facing your enemy openly. But the whole idea of Klingons using cloaks is basically an unfortunate artifact of Harve Bennett originally writing ST III with Romulan villains and then failing to change the technology when he changed the species.