My understanding is that Paypal is not accepted as payment for a virtual currency, mainly because of reversals but partially as it is against their policy.
How does Virwox get away with using paypal as a payment gateway for Linden dollars then?
Also, how long after a transaction is complete, does it take for a payment to become non-reversible?
Well, the generally accepted answer to that is six confirmations Each service can set it themselves. Most exchanges require six confirmations for bitcoin transfers, for instance. CoinDL, a digital download service, accepts payment immediately (on 0/unconfirmed). Others may give credit after two or three blocks, as the benefit to an attacker for that particular business (e.g., goods get shipped out to a physical mailing address) causes the transaction to be low risk.
0/unconfirmed can be sufficient for low value or high margin sales when 1.) the client does not accept inbound connections and 2.) the client explicitly connects to well-connected nodes. That is still vulnerable to a Finney attack though, so waiting for 1 confirmation lessens the risk of a double spend.
So it really depends on what type of transaction it is, and thus is there a reason to worry that an attacker would attempt to double spend on you.