Carriers price based on total revenue per subscriber, not just the profit per type of service. So, while the markup on SMS is high (might not actually be high), the RPU (revenue per user) covers total network costs.

As a cost, legal intercept isn't a drop in the bucket, and it has killed many an offering at a telco when they go to the regulator and the regulator says "you have to support legal intercept".

The cost structure behind SMS is typically due to many of the carrier's suppliers charging the carrier per subscriber (or per SMS). This puts a floor on the carrier's cost structure, and encourages them to look at any lever they can pull to keep new entrants out. Legal intercept would be part of the package. I have no idea how big a cost it is, but I would expect it to be a definite profit center for the equipment supplier - regulatory tends to be bespoke, special snowflake software that the customer MUST HAVE or else they will be turned off.

So, once a regulation is in, it's very easy to apply it as a barrier to entry. Imagine a mobile phone company starting up and not offering number portability.

There is even history in the telco market and messaging services, RIM (BlackBerry Messaging) ran into the exact same issues in the Middle East and India over the same thing [1].

[1] http://www.pcworld.com/article/216651/article.html