Margo:I put together a quick Console Application to test your MapServer Spatial Query.  I was able to get it to work with the following code ... (I apologize that it is in C# instead of VB.NET ... I can convert it if necessary)
            IPropertySet connProps = new PropertySet();
            connProps.SetProperty("Url", "http://www3.multco.us/ArcGIS/Services");
            AGSServerConnectionFactory agsSCFac = new AGSServerConnectionFactory();
            IAGSServerConnection agsSConn = agsSCFac.Open(connProps, 0);
            IAGSEnumServerObjectName pEnum = agsSConn.ServerObjectNames;
            IAGSServerObjectName pSOName = pEnum.Next();
            while (pSOName != null)
            {
                Console.WriteLine(pSOName.Name);
                if (pSOName.Name.Equals("BaseMap/Taxlots")) break;
                pSOName = pEnum.Next();
            }
            if (pSOName != null)
            {
                IName pName = pSOName as IName;
                IMapServer pMapServer = pName.Open();
                IMapServerInfo pMapServerInfo = pMapServer.GetServerInfo(pMapServer.DefaultMapName);
                IMapDescription pMD = pMapServerInfo.DefaultMapDescription;
                IPoint pnt = new Point();
                pnt.SpatialReference = pMD.SpatialReference;
                pnt.PutCoords(7682600.809, 681343.674);
                ISpatialFilter pSpatFilter = new SpatialFilter();
                pSpatFilter.SpatialRel = esriSpatialRelEnum.esriSpatialRelIntersects;
                pSpatFilter.Geometry = pnt;
                pSpatFilter.WhereClause = "PROPID = 'R311157'";
                IRecordSet records = pMapServer.QueryFeatureData(pMD.Name, 0, pSpatFilter);
                Console.WriteLine("Found " + records.Table.RowCount(null) + " records");
                ICursor pCur = records.get_Cursor(true);
                IFeature pFeat = pCur.NextRow() as IFeature;
                if (pFeat != null)
                {
                    Console.WriteLine("SUCCESS! Found Property: " + pFeat.Value[pFeat.Fields.FindField("PROPID")]);
                }
            }
That means that your map service is fine, and that there is something wrong in the implementation ... In my code above, I used a Point that I created instead of a Feature from a Layer in a Map.  That might be where your problem lies ...Hope this helps,-Kevin