The company must be registered in some kind of registry to be recognized as legal. For example, Registry of Legal entities.
Just ask the company to share public details of the company (company code, VAT code if exists, company address (registration or post), name and surname of the person you are now communicating with, contact phone or email, the registry where the company is registered, the country of such registry) so you could validate the company in that registry. If those details are not presented then I see no reason to go into deeper relations as hiding public data would mean they are hiding something that should be available for all.
After validating the company in the registry you should validate the registry itself. Some registries could be the same type of fake as some companies are. I do not know much about registry validation, but browsing google must be enough, I think - should be many many results..
That should be enough to validate the company. However, legal company does not mean you will be paid as expected. Even legal companies sometimes does bad things. :) You could search for creditability information of the company in the registries developed exactly for this. Such information could cost you some money, but it will usually provide a lot of useful information: number of employes, debt to government institutions (e.g. debt in taxes), income rate, etc. The deep and accuracy of the information depends on the registry. I am doing such creditability information on each job change (full-time job, I mean). I am from Lithuania (EU country) so I check such info at the registry of Credit Reform company: http://cr.lt/en/
I see they have some activity in Bulgaria, China, Germany, Estonia, UK, Italy, Croatia, Latvia, Luxemburg, Maldawien, Austria, Poland, Romania, Russia, Switzerland, Serbia, Slovakia, Slovenia, Czech Republic, Turkey, Ukraine, Hungary. I know nothing about their activities in other countries than Lithuania, so you should check it by yourself.