@ JetJockey, Meccti is a recruiter based in Ras al K. I have been told they ask for 4000 USD after you have been hired for Services rendered by them. I heard of some other Crew, Not applying to Omanair BTW, who suddenly got presented with a piece of paper with that clause in it. 4000 does sound awfully steep for presenting your CV etc.
I think the word is out as People are Bypassing them to go direct to the Company avoiding this problem.