What is the difference between the "complete" and " checkout complete" order statuses?
None of the above. You should be using hook_commerce_payment_order_paid_in_full(), which is always invoked the first time an order's balance drops to $0 or less.
Read more about it in commerce/modules/payment/commerce_payment.api.php.