Zen Cart's v1 architecture was built based on osCommerce architecture which wasn't designed to do as you describe.
The common workaround for it is to create a database table into which you store the shopper's session, and then do a callback which repopulates their session and only converts the session into a saved order after the payment callback happens. This does run the risk of a lost order if the callback never happens or doesn't complete properly. (This is how the old PayPal Standard module worked, and the need for the callback (and lost orders) is the very reason why we strongly discourage people from using that old style of gateway.)
Alternatively, since you've already changed the core code to pre-store an incomplete order, you could make your callback simply update the order details (change order's order_status field, and add to the orders_status_history table) instead of creating a new order.
Or, if your gateway is similar to Authorize.net SIM or First Data Hosted Payment Pages you could do as they do and use the receipt_url to notify the store of the payment completion without having to store the order first. This would require that your gateway be capable of emulating the Authorizenet SIM POST Return capability.
.
Zen Cart - putting the dream of business ownership within reach of anyone!
Donate to: DrByte directly or to the Zen Cart team as a whole
Remember: Any code suggestions you see here are merely suggestions. You assume full responsibility for your use of any such suggestions, including any impact ANY alterations you make to your site may have on your PCI compliance.
Furthermore, any advice you see here about PCI matters is merely an opinion, and should not be relied upon as "official". Official PCI information should be obtained from the PCI Security Council directly or from one of their authorized Assessors.