with regard to every other query failing, this is a 10.1 SP1 ArcGIS Server specific bug and affects identical queries fired sequentially using a GET.
[NIM086349 Alternate Query (Get) requests to some map services fail in ArcGIS Server 10.1 SP1.]
The problem has been fixed in 10.2. sorry for the inconvenience.