1994 they were definitely still free[1]. I had so many good ones, but when they switched to the paid model[0] I was a broke college student and let them all go.
[0] IIRC, it was Unilever who caused it -- they mailed in something like 19,000 domain registration applications, one for each of their current trademarks.
[1] OK, I looked it up, September 1995 was when the charging started.
Unilever later bought the domain substance.com from my friend. Remarkably, they apparently later let it lapse and someone else registered it. I'd assumed they were going to have a database of chemical substances that were used as ingredients, or something.