@animatedjay: Which is the playback state when you restart Strawberry or the whole machine, Playing, Paused, Stopped?
I'm running a Mini PC with Manjaro Linux as my "stereo" with a playlist containing the whole music collection in random order, Strawberry in autostart, and have "Resume playback on start" activated as well.
In Paused mode, restarting the program or rebooting the computer makes Strawberry starting playback immediately, in Stopped mode it also starts in Stopped mode again, so for me that option works as expected.