Regarding Paypal for Lebanon, I've done some research, and it seems that Lebanon has some "OFAC" (whatever that stands for) sanctions applied to it
BLOCKED:The assets of "persons undermining the sovereignty of Lebanon or its democratic processes" are blocked. Donations to these persons are forbidden.
Penalties: Criminal conviction can result in a fine of up to $1 million, and for natural persons imprisonment for up to 20 years. Civil penalties of up to the greater of $250,000 or an amount twice the amount of the transaction involved.
Although I understand that the penalties are only for cases where it is proven that the sanctions were
willfully avoided, and that the sanctions only apply to a set of persons (I couldn't find any names, though...), I infer that having Paypal in Lebanon will be an additional risk (and administrative expense) for them, because of these regulations.
I don't know about Egypt and other countries, and if there are countries with comparable situations (small and on the OFAC list), maybe someone else can look that up.
More details about Lebanon here:
http://www.treasury.gov/resource-center/sanctions/Documents/fr75_44907.pdf
Other links:
http://www.treasury.gov/resource-center/sanctions/Programs/pages/leb.aspx
http://www.bankersonline.com/ofac/ofacchart.html#LEB
PS: Two other American payment processing companies, 2checkout and Stripe accept payments from Lebanon, it seems, so it does seem to be possible to set up... I guess in this case the best way to stir the situation is sign up with the competition.
PS2: Paypal is avalaible in Egypt now (as of not very long ago), so maybe Lebanon is next.