Is there a way within Exp:resso Store to change the starting number on orders so they match my client's internal invoicing numbers?
If you order number is a simple number you need to start from such as 12001 you would just need to modify the auto increment start for the
ALTER TABLE exp_store_orders AUTO_INCREMENT=12001;
You should be able to run this in the Tools > Data > SQL Manager > Database Query Form as long as you have at least one order already in the system.
If you don't feel comfortable doing it with sql you can do it in phpMyAdmin or something like Navicat.
If you need an order ID that is numbers and letters you would need to either create an extension to extend Store's default behaviors or you could store the special order number in one of the custom order fields during the checkout.