The other option is to look elsewhere within the Gulf. People may say what they want about Serco, but I have always found that what they say you will get is what you will get, certainly no more, but also no less.
If the situation is as grim as what you say V8 then the other thing you can do is make sure you put the word out to any one else wanting to come from Oz or NZ that they will be screwed. The best way to get more in this part of the world is discourage the supply and so, as the demand increases so does your bargaining power for a better package. Here in the UAE Centre we were hugely short for a long time before we started getting 2,000 dh's per overtime shift and before the package was drastically improved (thanks again fox
)
Either way good luck.