I received a response from Shopify which was very helpful if anyone else needs the info:
Here is the background: There was a change in how the checkout process works in order to optimize the process and handle larger volumes of traffic without any issues or downtime. Part of this change was how checkouts are numbered. Prior to the change as soon as a customer started the checkout process an OrderID was generated, we’ve since switched the process to include a checkout ID during the checkout process where a customer enters their payment information, this checkout ID is what your seeing. The order number is now generated once a customer successful pays and generates a proper order.
The workflow for an order creation looks a bit like this: Product page (click add to cart) -> Cart Page (click checkout) -> Checkout Pages (creates checkout ID, clicks Complete my Purchase) -> Generates an Order ID.
You've raised a great point. And we're doing a couple of things to make this easier on you. First the checkout ID (the 8 digit number) is searchable on your shop by typing it in here: See image.
We've also taken that number, and displayed it in the order history to bring some relevance into the situation: See image.
The other thing we're looking into adding as soon as possible is adding a new column to the orders.csv export to include the checkout ID. At that point you'll be able to match it up with your info from your gateway.