Unfortunately, with the demise of TWA and AA's subsequent cancellation of their nonstop JFK/CAI route, Egyptair is the only airline with a nonstop flight.
That being said, I know that AA allows you to redeem 75K for a coach award on BA or IB to Cairo.
Swiss used to have good deals as well, but they recently changed their schedule out of Cairo forcing one to stay over night on the way back.
You can also try NW/KL. They usuallyt have some good deals as well. You could get airfare in the range of $700-$800. Alitalia also has some deals in that range.
Using miles is defintely goling to be tough, but depending on how you value your miles, if you were able to get airfare in the above range, IMHO, I would pay for the ticket. Just my $0.02.
Hope this helps.