I always use strongvpn.com whenever I'm in the UAE and it has worked flawlessly. No problems with Skype and other stuff that stupid Etisalat and Du block.
If you know your way around the horrendous red tape and have a bit of technical know-how, head over to openvpn.net, set it up on your machine and tunnel your connections through it and that would be free.
P.S.: Just occured to me that you probably won't be able to access any of the major vpn service web sites since they're already blocked by the shitty providers. Do you (or anyone you know) work at the DIC/DIFC? They have an open IP system that's not linked with the consumer network and you could probably get/buy a VPN connection through that.
P.P.S.: If you need something cheaper (and potentially less reliable), check out blackbytenetworks.com and witopia.com. Some of my business colleagues have used them in the past with fairly good success.