Preserving the order of status bar icons between restarts
You can try using Bartender, which keeps the order of the icons fixed (and does much more). It's a paid software, but it has a free trial and is available in Setapp.
So this was a bug - after a few months since opening it on Apple Feedback (while macOS 11 was in Beta 3 I think) I finally got reply this was fixed, and indeed so far in macOS 11.1 (build 20C69) everything seems to be back in order. Thank you to everyone who participated in this thread!