We're approximately the same age, and the first time I held job at which I had the option for direct deposit was 2003. I remember it particularly because I thought it was cool, and evangelized it to co-workers, many of whom did not trust it and opted to continue receiving paper checks.