SPATIALQUERY results are incorrect when used with an ArcMap Service

Description

Performing a SPATIALQUERY against an ArcMap service returns incorrect, or unexpected results. More, or less, features are being returned.

Cause

ArcMap Server may return unexpected results when 'envelope_intersection' is used within the SPATIALFILTER tag of a SPATIALQUERY request.

For example:

Code:
      <SPATIALQUERY>
        <SPATIALFILTER relation="envelope_intersection">
          <ENVELOPE maxy="30" maxx="30" miny="0" minx="0" />
        </SPATIALFILTER>
      </SPATIALQUERY>

Workaround