It certainly does sound to me like the shift interlock. The fact that it will mostly happen after sitting for a long time makes perfect sense if the device is sticky. I don’t know the specifics, but its probably something like a little lever that blocks the shifter. The lever is probably moved out of the way by a little solenoid. If it is just sticking from contamination, old grease, etc. then when its been sitting a long time is when it will get stickiest. Once its gotten itself moving its not stuck anymore. The same thing used to happen to the Tin Man.
I know that you mentioned always putting your brake on. But if the brake light switch has a problem or if the locking mechanism is sticky this isn’t relevant (except of course that without pressing the brake you’ll never get it moving).