My first 'domestic' sector on the 767 was MEL-OOL on 2nd November 1993.
I'd been an F/O on the jet for a few years before that with no other domestic sectors other than the tail end or beginning of an international service (e.g.: SYD-BNE-POM-BNE-SYD), so I'd be surprised if we started much before that.