You're right. The first paychecks in my current gig were paper. Part of the hiring paperwork was giving them a voided check to set up the electronic deposit. It might have taken a month or so to kick in. I forget how, or when I got hooked up, but the previous one was digital also.
My brain may be turning into tapioca, but fortunately, there's no way for me to get a spoon in there...