Do I understand correctly that...

-the employees are refusing to guarantee their own liability for charges on the company credit card that they are using
-the employees are requesting a corporate credit card that provides some kind of bonus (i.e., miles)

If I were the employer, I would say take it or leave it. The employer can return to a format where the employees pay their own expenses, and get reimbursed after an expense report is filed.