** This issue has been resolved in ArcGIS 9.0. **
When querying against an ArcMap Service the performance is slow.
This is a known issue. When the field being queried against belongs to a .dbf table that is joined to the layer, performance speed is reduced.
There is no workaround at this time.