Get all messages from Outlook API

I'm consuming the Outlook API, attempting to access all messages from an inbox which contains ~45,000 messages (and other folders such as Sent Items).

The main request I'm making is to https://outlook.office.com/api/v2.0/me/messages. If I add ?$count=true, the "@odata.count" value is returned as -1.

I can add $top=500 to the request which gives me 500 messages returned and an "@odata.nextLink", but if I pass $top=5000, there's no "@odata.nextLink" which I'd expect to see.

A few particular questions here if anyone can help:

1. Is this the best way to try and get all the messages out of all folders?
2. Is there a reason count would be returning -1, and is there a way to get an accurate figure of the number of messages returned?
3. Is there a maximum $top size I need to pass to get a valid request back?

1. Yes, but understand it includes Drafts, Deleted Items, and Sent Items in addition to all of the other mail folders.
2. This is a known issue with /me/messages. Basically the way that /me/messages gives all messages across all folders is by using a search folder, which dynamically updates. The API doesn't report accurate counts for search folders (usually just returns -1).
3. The highest $top should be 1000.