Do you believe in ISO/IEC 27001? Do you accept that a company that is implementing and maintaining a management system based on ISO/IEC 27001 will have effective information security management processes?
If you don't, then its pointless worrying about how we can trust certification bodies, like BSI. A lot of people don't understand the standard in the first place - thinking that it is all about IT, or that if there is a major security incident then the standard, or certification body, have somehow failed.
In fact the biggest problem, in my opinion, is in the implementation and around the inappropriate scoping of the ISMS - most commonly its the inclusion of the IT department at the expense of everything else called the 'actual business'! A true recipe for wasting time and money and one I hope will be less encountered with the release of the 2013 version of the standard.
Put another way, having ISO/IEC 27001 certification doesn't mean that you have good information security, as that will depend on many factors. What it does mean is that the organization has established an ISMS, is implementing and maintaining that ISMS, and that the ISMS is reviewed and improved on a continual basis. The role of the auditor is primarily to 1) check for conformity to requirements, and 2) to assess the effectiveness of the ISMS - i.e. is it consistently achieving its policy objectives.
In certification, you are putting your faith in the abilities of the individual auditors that carry out the audits on behalf of the certifying body. If two different and competent auditors plan and conduct the same audit, both will emerge with different findings. In order to have confidence in this process, you must also understand how it works, its value and its weaknesses.
As was mentioned earlier, national accreditation bodies like UKAS help to give us that confidence by auditing the certification bodies, essentially on our behalf, and removing the accreditation if the certification body is not fulfilling its own management system requirements and complying with standards such as ISO/IEC 17021 (Conformity assessment requirements) - which, for example, requires that certification bodies and their auditors are independent in conducting the audit. How many certification companies do you see that also provide consulting services? Consulting and auditing are two complete opposites, and will invite bias in the audit result. Accredited companies like BSI are not allowed to provide consulting services.
Another important requirement is that certification bodies must have an effective processes in place for selecting and training auditors that ensures the necessary competence - very important as I mentioned since we are being audited by people, and all are different. Good certification bodies will ensure consistency as much as possible, and to a high standard.
So to answer the question, we trust in 'accredited' certification bodies because we understand that they are being monitored by a competent, independent third-party and have to maintain certain standards in order to remain accredited.
Are there good and bad certification bodies? Are there good and bad auditors? YES to both! Its grey, and as mentioned earlier by another poster, its a convention of trust. Ultimately, I think it is the reputation of the certification body that we are looking to for that trust and is the main reason why the original poster's (op) certificate is perceived as being worthless compared to the certificate of the known certification organisation.
One more note on this point, there is no 'requirement' for certification in the standard. Its a choice a company makes for [mostly] outwardly building confidence that they are committed to the process - why I asked in the beginning, do you believe in the process?
Equally, anybody (me, you, and the op) can conduct and certify that a company is conforming to the ISO/IEC 27001 standard - nothing wrong with that, depending on the benefits that the organisation are looking for. Certainly, an 'unaccredited' certificate from the op will not hold much weight in the community view, but bare in mind that it all comes down to the auditor, and there is no reason why the op or anyone else couldn't be sufficiently competent and experienced in conducting ISO/IEC 27001 audits and be in a position to provide great value to an audit client by providing an independent opinion.
Why do we trust in the organizations that certify ISO/IEC 27001? Maybe for the same reasons we trust in SSL Certificate Authorities - Reputation.
Just an opinion..