Toolbar changes are saved when you exit Rhino. It is not necessary to save the file.
Toolbar changes are also saved immediately via Options->Toolbars->File->Save as you noted, which can also be run as a macro: ! _-Toolbar _Collection _SaveAll _Enter _Enter
The thing is that if you have more than one instance of Rhino open, each one that exits saves (overwrites) the existing toolbar file. So if you make changes in one, then exit, but another instance is running which doesn’t have the same changes, when you exit that, the changes made by the first instance exiting will be lost (overwritten).
A corollary is that if you make changes to the toolbar file in one instance and do not immediately save those changes, and then open another instance (while leaving the first instance running), the new instance will not have your changes from the first instance - as they are only saved when you exit the instance or force an immediate save as outlined above.
The takeaway: Only modify your toolbars with only one instance running. Then force save your changes immediately to make sure they are applied and you don’t forget and open a new instance before doing so.