For the past umpteen years most of my business travel has been under a policy of I pay for it upfront, sans corporate charge card, and file for reimbursement of actual expense. I've used gift certificates multiple times. In many cases on the receipt they look just like any other form of payment, such as a credit card. There's never been a clause in my employers' company travel policies that restricts method of payment; only that the expense incurred is appropriate and adequately documented.