From this article:
In July 1992, New Jersey’s Supreme Court overturned state kosher regulations that defined kosher in terms of “orthodox Hebrew religious requirements,” ruling that it violated the constitutional prohibition on the establishment of religion.
New Jersey now operates under a “full disclosure scheme,” whereby manufacturers or purveyors of kosher food must fill out forms indicating what they sell and under whose authority. The forms are filed with the state and posted for public view, so consumers can decide for themselves whether to patronize the establishment.
The disclosure form is careful not to make religious judgments. Purveyors must state, for example, whether they sell pork or shellfish, or mix milk and meat, but they can still call themselves kosher, as long as they don’t conceal these facts.
“You can put down absolutely anything in the world you want,” said Rabbi Yakov Dombroff, who has headed New Jersey’s Bureau of Kosher Enforcement since 1986. “Literally, pork could be kosher. The state has no interest in what you call kosher, as long as you’re in compliance with the disclosure.”
As the article explains, this is also the case in New York and Baltimore. Since the article is a couple years old, it may also be the case in Georgia by now, and who knows how many other states.
(Sue Fishkoff goes through the history of this Supreme Court decision in her book, Kosher Nation)
So basically, just because a restaurant says it is Kosher is no guarantee that it is actually Kosher.
On the other hand, the major reliable Kashrut organizations policies are well known, easily accessible, and consistent. Once you do some research on the Kashrut Organizations policies (usually all available online) and figure out if they line up with your Kashrut sstandards, you can decide if you will eat the food with that hechsher.
For example, The OU relies on a leniency of R' Soleveitchik and does not require a constant Mashgiach for fish processing (except for Pesach), whereas the Star-K does not rely on this leniency, and does require a constant Mashgiach for fish processing. (I just linked to the policy. Sue Fishkoff mentions that the OU rely on a leniency from R' Soleveitchik, but I haven't found this explicitly, although it is also mentioned here.)
So, before you go to the store you know that the OU certifies tuna without a constant Mashgiach. If you're alright with that, you will buy OU certified tuna. If not, you won't. But you know going into the store exactly what to expect from tuna with an OU certification, since the OU's policy is well known, easily accessible, and consistent.
Kashrut organization rely on trademark protection to ensure compliance. For example, the OU symbol is trademarked, and the OU gives permission to companies who comply with their guidelines to put the symbol on the product. An unauthorized OU is a trademark violation and the OU can force the company to recall all the products with the unauthorized OU, at great expense to the company. This helps prevent fraudulent claims of Kashrut, and furthers our trust in the reliability of the hechsher.
All that being said, when encountering a new product, I think the consumer should always proceed with caution. If it sounds to good to be true, it may well be. One should check with the website of the Kosher organization and see if the product is truly certified. Products are sometimes accidentally mislabeled, and alerts are issued to let you know.
Even once you know a product is kosher, you should still verify that the hechsher is still on the packaging, since products lose or change their hechsher all the time. It may also happen that some production runs of the product are certified, and some aren't.
Also, depending on personal stringencies, it may happen that someone won't eat certain products from a perfectly reputable Kashrut organization. For example, if someone strictly eats Bishul Yisroel, he should check the ingredients to ensure that the Kosher product does not need to be Bishul Yisroel before he eats it (e.g. corn chips).