I registered my personal domain in the summer of 1999. I vaguely remember that Network Solutions was the only option (you had to fax them) and for .org I would have needed to provide some additional justification. Maybe that changed after the monopoly was broken?