Thank you Xander for pointing out this.
I did try the Within relationship but I came out to another issue which seems to be the main one.
Trying to count the features is OK :
http://landsat.arcgis.com/arcgis/rest/services/Landsat8_Views/ImageServer//query?&f=json&where=Categ...
Retrieving all the features is OK : http://landsat.arcgis.com/arcgis/rest/services/Landsat8_Views/ImageServer/query?f=json&where=Categor...
But when using resultOffset=0 and resultRecordCount=20 for example, nothing is returned.
http://landsat.arcgis.com/arcgis/rest/services/Landsat8_Views/ImageServer/query?f=json&where=Categor...
Documentation says that the resultOffset and resultRecordCount parameters are available for 10.3.1 only but they actually do work when using the Intersects relationship.