Fischer, does your AVR have Dynamic Volume? If so, and if it's turned on, the relative volume of your surrounds will be higher (compared to the mains) at low volumes, which can sound like a bigger soundstage at lower volumes than at higher volumes. Maybe that's part of what you're noticing.
What materials are you listening to when you notice these various changes in soundstage at different volumes?
I have the Dynamic Volume off, I experience it both when I listen to music and run regular stereo and with movie and multi-channel audio,
I experienced the same variations on my previous preamp Onkyo PR SC 5507, so that is why I ask if there is some kind of known software bug of Audyssey!
There is no known bug that causes variations in results from different measurements taken in the exact same circumstances. Move the mic 1 inch and you may get variations.
What, specifically, are you referring to by way of variations?