I use Skype from the UAE multiple times daily.

Skype-to-Skype works without any issues.
Skype to phone works using a basic free VPN service.

Sometimes you can sneak a Skype to phone through the Etisalat/Du firewall (more often with Du than Etisalat), but don't count on it.