Replying to [detronic]:
With the tax number check is good also to check the Chamber of Comers per country.
In 99 % of the EU countries the company MUST have a registration in the Chamber of comers.
In some of the sites you can go inside the registers free and check for address registration ,and registration number. Together with the tax ( VAT,BTW) number is enough for a start.
BUT dont give as well 100 % guarantees.
Registering a company in Holland, special one man company for example is quiet easy and actually really fast. Cost really little and actually you get your registration number in the Chamber of Comers. If you register in the blank Export- Import ,you can make your application for BTW number as well and you will have it after a 2- 3 weeks.
SO ,main point is IF possible visit the company, meet the people ,AND dont look for big buildings and shinning offices-it is not a guarantee for nothing. And Second :
Talk with the Chamber of Comers, before the trip to find out how old is the registration it self . They probably will not provide a information like this on the phone BUT probably will support you ( after when you explain the situation) to give you a clear indication and confirm are the company exists from more then a week. Combination of this two things I think is the best solution.