Clearing out some old books, I found this from 1997. It’s a Telstra brochure explaining a new product they’re introducing: the “SMS Text Message Service.”
Everything was new once upon a time, right?
From the brochure (and this matches my recollection), initially messages could not be sent between operators. This didn’t come until April 2000, and predictably resulted in exponential growth in messages sent.