I know this is a bit stale. I just ran into the same issue and found that if I removed docType="html-5.0" I was able to successfully submit it.
Two examples - this one fails:
<apex:page standardController="Case" docType="html-5.0">
<apex:form>
<apex:pageBlock>
<apex:actionRegion>
<apex:inputField value="{!case.multiselect__c}" required="true">
<apex:actionSupport event="onchange" rerender="fields" immediate="true"/>
</apex:inputField>
</apex:actionRegion>
</apex:pageBlock>
<apex:commandButton action="{!save}" value="Save"/>
</apex:form>
</apex:page>
This one passes:
<apex:page standardController="Case">
<apex:form>
<apex:pageBlock>
<apex:actionRegion>
<apex:inputField value="{!case.multiselect__c}" required="true">
<apex:actionSupport event="onchange" rerender="fields" immediate="true"/>
</apex:inputField>
</apex:actionRegion>
</apex:pageBlock>
<apex:commandButton action="{!save}" value="Save"/>
</apex:form>
</apex:page>