Had this problem with my CCs as well. Wasn't sure what the problem was, so I waited a while but the problem persisted. I then called up AmEx member services and they explained that there had been a lot of fraud going on with stolen CCs in the region, so me booking airline tickets from Dubai apparently triggered their anti-fraud systems.

Since then, I've never had a problem.

So, maybe call your CC company and ask them if they are denying it for some specific reason?