Cheapest way to get to BEY (as to other places in the Middle East, such as AMM, CAI, DAM) from Cyprus is actually to go for a flight+hotel package. There are several tour operators that do these from Cyprus, have a look at my post in this thread:
http://www.flyertalk.com/forum/showthread.php?t=546743
Right now, for example, Amathus offers 3 days (not sure if 3 or 2 nights) to BEY incl. flights and hotel for CYP110 per person (USD245) but I think taxes are on top of this.