I believe that at a kosher shiur I attended with a lecturer from one of the big agencies, he mentioned that kashrus agencies rely on each other for certain basic ingredients such as flour, sugar, salt, spices, etc. Each organization does not have to supervise the production of each ingredient. As long as each ingredient used in the production of the products they supervise has a good hechsher IF it needs one, then its fine.
The companies under supervision must list all their products and submit them to the supervising agency for approval. I believe that by means of their contract, they are not allowed to switch ingredients without approval of the supervising agency.
The reason we find out that things are mislabeled or that things are no longer under a certain supervision, can be attributed to the fact that the agencies are doing their job and inspecting, investigating and supervising. In some cases it is just a matter of shopping for the best price a company can get for supervision.