I would only buy from retail dealers on Ebay not individuals. They would have thousands of previous transactions, and any problems other buyers would have posted negative reviews. Plus they usually have some type of return policy.
There is no real way of verifying if a cell phone is legit.
You can always ask for the phones ESN to see if it was reported stolen, but it would only help if the original owner had reported it. Usually people don't report the phone stolen right away in hopes that they will find it. Unfortunately during that time the thief will try to sell it while it still has a clean ESN.
I bought my S3 from a dealer on ebay and it is perfectly fine.