How to change order_number on hook_commerce_payment_order_paid_in_full or hook_commerce_checkout_complete
I don't think it's a good idea to change the order id. 

I would rather goto admin/commerce/config/order/fields and a new number field which will be used to store the 3rd party's order id in the field.

That way you are not changing the default workflow of Drupal commerce and it will also be easier for you to compare your order id against the third party order id if something goes wrong.