How are you booking your tickets? I still book mine as just Last/First
I can't use my AMEX to check-in at a kiosk because it sends my name as Last/F instead of spelling out First.

Are you booking your tickets as Last/FirstMI and since your CC doesn't send MI it's failing?

...don't put the MI on your tickets then!