We have created a new payment method for our gift card, we then take the following steps in Magento.
1) Retrieve Gift card Balance through Ajax call
2) We then display message as per available balance.
If balance is sufficient - "Please continue to confirm order"
If balance is not sufficient - "Please insert credit card info in order to pay XX remaining amount"
3) Customer fills in CC info and then presses continue.
4) At the place order step, when the customer clicks on place order button, we will Authenticate GC amount and check latest available balance in capture function of Payment Gateway, if it is same as Payment step then we can directly capture the remaining amount from the credit card.
If a difference arises in GC balance then we show a message and confirm with customer that they would like to pay XX amount from CC or wanted to use new Credit card for all remaining amount.
And it works!
The same logic should work with Money Order/Check + Credit Card (Since we won't have to check the balance on the Check