This is a very difficult problem. It is sometimes refered to as the "level of assurance". In fact, it can be further divided into the entity (i.e. person, company etc) level of assurance i.e. the level of assurance you have that the information about the entity is accurate and correct and the identity level of assurance, which is the level of assurance that the identity using that information is the same identity that is associated with the entity.
A common example of the entity assurance is the 100 points system used by many organisations to verify a person i.e. photo ID, passport, driver's license etc. Each bit of information is given a score based on how reliable the information is for proving someone is who they say they are. A passport may be worth 50 points, a birth certificate 10 points, a drivers license 20 points etc. The person wishing to prove their credentials must provide enough proof to add up to 100 points. This establishes the entity level of assurance. This normally needs to be done in person so that you can verify the photo on the passport/drivers license etc represents the person presenting the proof.
Identity level of assurance is used to prove that the person using an identity associated with an entity is that entity. For example, when you connect to your bank. Often it is achieved with something like a password (least strong) or a combination of things (password plus unique token pous some form of biometric data, such as a finger print (something you know, something you have and something you are).
In your exzample, you probably have a need for both entity level assurance and identity level assurance. Some sites don't have such requirements. for example, facebook and gmail have very low entity level assurance - they trust that the information you provide is true. However, they have increasingly strong identity level of assurance, for example, adding 2 factor authentication.
Normally, any site which reuires high levels of entity level assurance will also require high levels of identity level assurance i.e. if you require the user to provide true and accurate information, you probably also need to ensure anyone logging into the system as that person is actually that person.
Identity level of assurance is usually easier to achieve than entity level assurance. Entity level assurance is very difficult to achieve remotely. Normally, you would require the individual to be physically present so that you can do things like verify the photo on a passport, license etc matches the person standing in front of you. When this is not possible, you usually need to rely on some form of 3rd party to assist in your vetting process. This could be something like a partnership with an organisation which has a large number of public offices - for example, a post office. You might pay a fee to this 3rd party for them to provide a vetting process. An individual wanting access to your service would then need to visit the post office, provide their 100 points of proof and then the post office would provide you with their details and sign off that they have vetted this person with the level of assurance you require. Obviously, you are trusting in this 3rd party. Another alternative is to use a certificate authority. Most of the CAs provide a personal certificate service. The individual purchases a personal certificate from the CA. The CA performs the vetting prior to issuing the personal certificate. Of course, the risk with all these 3rd party solutions is that your trusting they actually do a decent job. As vetting can be an expensive process, some CAs do a better job than others. If you reduce the rigor associated with the vetting you can reduce the cost and in turn provide cheaper certificates, thereby gaining a competitive edge. However, this may result in less confidence/trust in the certicates that are issued.
The other problem with certificates is that it relies heavily on the person managing their certificate in a secure way. If someones certificate is stolen and either it does not have a passphrase/password associated with it or if the thief was able to get the passsword/passphrase, then they can use the certificate and effectively impersonate the user it is associated with.
This all probably makes your problem seem impossible. However, things may not be as bad as they first appear. We often fail to really analyse our requirements and have many inherent assumptions about what we need. It is important to consider that the more personal information you require and the more accurate it needs to be, the more expensive it will be for you and the more inconvenient it will be for the user. It will be more expensive for you because of all the additional safegurds you will need to implement, which means more complexity, which means more development, more testing and more maintenance. For the user, it means more hoops to jump through and most likely, more concerns regarding using your service etc.
In additional to considering whether you need the information, also consider whether you really need it to be 100% accurate. For example, if you require their date of birth, how are you using that information? What is the impact/affect if it isn't accurate? What will the users impression be when you requirest that information? etc.
After you hve gone through all the information and assessed it along these lines, if you find you still require a high level of assurance, then you can look at options such as requiring a certificate, establishing relationships with 3rd parties who can assist in your vetting etc.
Finally, note that your example of faxing/mailing in copies of certificates probably won't be sufficient. I could easily obtain birth certificates and possibly passports, drivers licenses etc of someone else and fax them to you. While these certificates may be 'real', there is nothing that proves the person who sent them is the person the certificates represent. Likewise, if you decided to use something like OpenID or some form of social media authenticaiton, you need to look at what the vetting levels of that identity provider are to know if they are sufficient for your needs.