On Background Verification My Previous Company Is Marked As Fake

I have started my career with a small company consists of 8-10 employees and worked for 1 year. That company is not fake, its a small company and is there from last around 15 years. After that I have joined another company and worked for 3 years. Now when I am trying to change the job and in background verification, the verification team is saying they(My First Company) is not replying emails from the company domain rather sending from gmail. This seems a fake company. How would I convince them, this is not a fake but only a small company. What steps can I take if they tell me that this is a fake company.
Your inputs would be invaluable for me.

Give the address and physical location of your old company.
Give the names of some top employees there who know you and can speak abut your work there.
Just because a company replies using Gmail domain does not mean company is fake.

Thanks Nathrao, Thanks for your quick reply. I have already given them the physical location, they are planning to visit the old company this week only. But for this whole week, my old company is closed due to diwali vacation. Will that impact the verification process, if at the time of physical verification the office will be closed, Do I need to inform them, the company is closed for this week.
Thanks in advance,

Take pro active action to inform about Diwali vacation.
Cross check whether verifying agency has physically visited or not.
What type of documentary evidence have you produced-salary slip,bank statement of your salary etc?

I don't have bank statement, my salary was very less there actually. But I have provided relieving letter as per their requirement. They have not asked me for any other document rather than relieving letter. Will inform them pro actively about the diwali vacation.
Thanks Nathrao, I can't thank you enough for your time and effort. Bit relaxed now.

It is always easy when you speak or submit what is truth and honest employment details.Get your former boss/manager to speak and be a reference for you.
Things will work out.

The HR of your company should not keep sitting in their office by restricting their activity of verification only up to sending email. If no reply is received, they should move out to check physically with the company, rather than presuming the previous employer as fake.

Dear JRP1414
I agree with the views expressed by our senior member Mr Nathrao.
Try to locate all written evidences like Salary slip, Appointment letter,
PF detail( if any ) ESI detail, any photographic eveidence, experience certificate
( if not available try to get one).
All these will be useful for you in future employments / job change also.
V.Raghunathan

you even can take the hard copy of the verification form and go to your previous company and get the verification done and submit the report to Hr Dept.

Hello JRP 1414,
Is your First Company a Private Limited Company or Partnership or Proprietorship?
IF it's a Pvt Ltd Company, go to the MCA website & search the name of this Company......you should get the results WITH the active Directors & their DIN Codes. Just take a Screenshot of this & mail to the new Company's HR guys.
You mentioned 'verification team is saying........'. Does the team belong to the Company OR an Agency?
Usually, Contact numbers ALONG WITH the Mail IDs are asked for BCs......haven't you given your earlier boss's or MD's contact #?
Rgds,
TS