Well, after some time I am now quite confident that the volume change is caused by the 3rd party driver we are using. This driver has it's own volume control mechanism. I do not experience the change anymore after just starting the drivers' control GUI. Even after a restart the problem seems to be fixed. However, after some time it gets broken again for a reason I cannot figure out. But this only happened because some security settings prevented the drivers' control GUI to start when logged in as non admin. I fixed this now and expect everything to work now.
Furthermore it looks like that all user sessions share the same volume control. That means if I change the volume with SndVol in one user session the same change happens in the other user session. My service receives notifications for all these changes. So it looks like that I did not receive a notification when switching between users because the change was caused by the driver's control GUI starting when logging in as administrator. But this change happened in the driver, a lower layer, so that Windows is not aware of the change.
The driver we are using is the kX Audio Driver.