This forum is not the place to voice personal disputes. By complaining, in public, about the services rendered (justified or not) you expose yourself to a lible lawsuit. Point 1: Resolve your conflicts in private.
Paypal does have a dispute resolution policy, but it generally always favors the person receiving money when dealing with contract work. Paypal doesn't get involved with the legal matters of what was agreed to in the contract, and basically will force you into the legal system to get the money back. Their general policy on contract work? If you paid it, you must have liked it at one point. Point 2: Know your payment systems.
Have an agreement in place. I can't stress this enough. If you're working with a contractor on an hourly basis, you're pretty much liable for everything they claim they did unless you can prove they didn't actually work when they said they did. If you're on a fixed bid project, expect to pay a significant portion down as a non-refundable deposit. I don't know the specifics of this situation, but it seems to me that your contractor took a deposit, and did some research. That is legitimate billable time IMO. Unless your contract specifically stated that he can't bill for this time, you really have no legal recourse to claim fraud. I personally have lines in my contracts outlining the work to be done and "other web related activities required to complete the project" which includes r&d. No agreement = no fraud. Point 3: Have a contract
Be clear about your expectations up front. I can't tell you how many times in the past ten years I've had clients come to me for "simple" fixes, then ask for more and expect that to be within scope. A good example I use is a login form on a site. Part of the project will have a requirement like "The user needs to be able to login with a username and password". This can reasonably be implied to mean that there will be a form with a username and password input fields which will validate against a list of active username / password combinations (either a static one, text file, database or something else). However, even this "simple" task gets complicated when the client starts adding things like "I need the system to only allow 3 login attempts, then block them for 24 hours" or "I need the system to not be case sensitive with the usernames" or "I need the user names to change to emails" or "I need max of 3 login attempts, then display captch for 2 more attempts, then block the user". Point 4: Be EXPLICIT in your requirements.
Now, I'm not going to sit here and say that the programmer is always right. That's clearly not the case. Nor am I implying that the client is always wrong. But I am saying is from what I've read so far in this thread, I do not see clear evidence of fraud based on my experiences in the past decade, but a breakdown of one of the 4 points above.