SearchByCriteria in V2 API not returning all records

SearchByCriteria in V2 API not returning all records

We have used your SDK to convert from V1 to V2 API calls.  We are testing the conversion and have noticed that SearchByCriteria does NOT return all expected records. 

Here are a couple examples:

This search only returns 4 records while it should return 13:
GET https://www.zohoapis.com/crm/v2/Sales_Orders/search?criteria=((Subject:starts_with:Wendy))&page=1&per_page=200

This search returns 0 records and should return 1 by the Sales_Order_NO
GET https://www.zohoapis.com/crm/v2/Sales_Orders/search?criteria=((Sales_Order_No:starts_with:SO106883))&page=1&per_page=200

Is there something wrong with the way we are building the criteria or does something prevent all records from being returned? 

The current V1 API still works as expected but it will stop working at the end of the month.

Please advise.