Presumably because the Federation got something from the Romulans in exchange for agreeing not to develop or use cloaks, something worth more to them than cloaking technology.
I see the Treaty of Algeron as something like the Nuclear Non-Proliferation Treaty, of the 189 parties to the treaty, only 5 of the parties "get" to have nukes.
The Romulans had some kind of advantage over the Federation at some point and slid the treaty under the Federation's nose to be signed. Did the Federation get anything at all in return, was there a package deal? We certainly never heard of anything.
The Federation's ability to penetrate the Romulan's cloak is hit and miss. In Unification, the Romulan warship trailing the troop transports was a complete surprise, even though the Enterprise was right on top of it.
Starfleet occasional couldn't detect the Romulans, the Romulans could always detect them.
And it isn't just a matter of the Federation and the Romulans, Starfleet is apparently not allowed to use a cloaking device in confrontation with anyone! The earlier protracted war with the Cardassian might have ended sooner, with fewer causalities on both side, and more advantageous for the Federation, if Starfleet had merely been permitted to employ a cloaking device during combat operations.
Voyager certainly could have used one.
It hard to see the Federation agreeing to a treaty that put them at such a disadvantage, unless they had no real choice in the matter.