Today I had this problem and I wanted to share the solution with you. I know personally how frustrating it can be to spend hours on an issue that has no reasoning for it.
Basically I created a Fetch XML report. The fetch dataset was only returning 500 records when it should have returned 2000 records. Now fetch datasets have a page size of 5000 and therefore would only return a maximum of 5000 records BUT there was no reason for the dataset to return only 500 records.
The fix is simple, change the root fetch node to have a count of 5000 as per the below example.
