It was a stupid mistake on my part. The setting "Maximum Number of Records Returned by Server" in ArcGIS Server Manager was set to 500, whereas much more than that was returned, and it ended up showing that no records were returned. I actually got records when I increased the maximum number of records returned.
Maybe in future versions an exception could be thrown, instead of show that no records were found? 😛