You can't set it any higher as that will be the limitation of the DAC and ADC within the headset. USB can support higher, but it depends on the implementation. With an analogue headset, you can set it to whatever the audio output device (onboard audio, sound card) can support. USB audio devices have a built in sound card, if you like, so that will determine what the maximum quality setting will be within Windows. In the case of the Cloud II, the DAC and ADC are likely 16 bit 48000 Hz.
It's odd though, because I've never known changing the microphone quality setting from anything above 16 bit 48000 Hz (CD quality), to make any significant difference. My Logitech desk microphone can't be set any higher than 16 bit 48000 Hz, as like the Cloud II microphone, that's the limit of the ADC; I've never had any complaints of poor quality when talking to friends.
I don't know whether it's possible that your last headset had a pretty rubbish microphone and increasing the quality helped?
With a decent enough microphone, CD or DVD quality should be more than enough.