I flew with these some years ago from Pafos
http://www.griffonaviation.com/
Aeroplane was a PA28, tatty looking but fully serviceable. It gets very bumpy due to thermal activity and you have mountains rising straight off the sea. You wouldn't want a forced landing I can tell you.
Chart was a photocopy and you needed a FP for every flight.
No idea what they are like now but if they're still in business they must have something going for them.