I would gather enough information from that new sign-up user, and verify any related data with that information (from the IP address, country, etc.).
If everything is ok and all information seem to be valid then go ahead to accept the order.
As far as paypal goes nothing is guaranteed. If you are in hosting or any other digital goods business expect some losses every month in paypal. As far as accepting paypal paymnts goes Id advise to accept verified paypal and make sure the email and other info match the paypal.
May be you can notify client situation and ask him to provide his legal identity like credit card copy, that way you can verify if it is real client or fraud order. And yes, matching location and ip is best way.
If the order seems suspicious, don't accept it or ask for more information. Being an unregistered PayPal order (which just means he ordered with credit card via PayPal, I think?) is probably lower fraud risk than being a real PayPal account, since it seems those are stolen 50% of the time anyway.