Interesting set of problems, but not so sure they are specific to Gulf Air; I would hazard a guess that they almost certainly apply in most of the airlines in this region currently.
Politics: Ubiquitous in any company in any industry these days.
Wrong People: Probably GF has more than its fair share of this. The problem has a history and the labour law does not help.
Corruption: Prove it. If you can, use EthicsPoint but be prepared to substantiate your claims.
Payouts: VRS? Nothing wrong with the VRS other than a boat load of people who applied were not let go which is a shame - the company still maintains far more than its fair share of dead wood.
Staff Travel: As all but one route are eligible for electronic tickets, 99% of staff travel should be done on-line so use it and don't expose yourself to the pain of a visit.
Morale: Crawl out of it! Making the effort to be positive can have a long reach.
Getting away with it: Use EthicsPoint but be prepared to substantiate your claims.
Organisation: Agreed too fluid still; 8 months into the latest game and still departments cannot get their organisation set.
Reports: If they are genuine, what's the (your) problem?
Costa: I bet the revenues are nowhere near what they were a year or more ago. I bet they are 50% of the JH era.