I am using the standard http based REST API via Xml (i.e. not APEX or SOAP) and so the QueryAll() method is not available.

I have tried various queries but can't get this to work..

What am I doing wrong here..?

SELECT Id, IsDeleted FROM Account WHERE IsDeleted=true

<QueryResult>
  <done>true</done>
  <totalSize>0</totalSize>
</QueryResult>

SELECT Id, IsDeleted FROM Account WHERE IsDeleted=true ALL ROWS

<Errors>
  <Error>
    <errorCode>MALFORMED_QUERY</errorCode>
    <message>ALL ROWS not allowed in this context</message>
  </Error>
</Errors>