I've heard that Rav Soloveitchik ztz"l used to eat non-hekhshered cheese. Can you explain how the creation of hashgachah agencies has changed whether things need hashgachah, and would it be reasonable to argue that plain, non-hekhshered cheese (without added things in it like peppers) may be asur l'akhilah but doesn't actually tref dishes?
This is not a question of "does product X require certification", it's much more complex than that.
The Gemara says that "cheeses of non-Jews" are non-kosher. The prevailing opinion is that out of concern for intermarriage, the rabbis absolutely prohibited all cheese if the milk was owned by non-Jews at the time of curdling, or if the rennet was added by non-Jews. Any kosher cheese certified by OU,cRc,Star-K, and the like today was owned and curdled by Jews.
There had been another interpretation of that Gemara that it was a concern regarding the rennet's animal origins. But many mass-produced cheeses today use microbial rennet or the like. Hence, anecdote has it that when kosher cheese was unavailable in his early years in Boston, Rabbi Soloveichik followed this interpretation and ate cheese that definitely did not contain animal rennet.
May I note that Rabbi Soloveichik was a brilliant Talmudic theoretician, whose school of thought was often to follow whichever longstanding interpretation he felt was most correct, even if it was viewed as more of a minority opinion by most. (For instance, the standard of Shulchan Aruch is that the visitor follows the practices of his hometown vis-a-vis second day of yomtov. This is the opinion taken for granted by Rabbi Moshe Feinstein among many others, and if anyone asked me, that's what I'd tell them too. Rabbi Soloveichik felt that R' Yaakov Emden's dramatic reinterpretation (visitor follows current locale) was correct, but also adopted some stringencies of the better-regarded interpretation, out of respect.)
So your question isn't "if a non-certified product falls into a mixture, how (un)certain am I that it contained non-kosher ingredients." It's "now that we follow the prevailing view of the rabbinic prohibition on non-kosher cheese, is there any room to follow other views in rare occasions ex post facto"? My sense on that is that once majority opinion codified into halacha that all cheese made by non-Jews is non-kosher, we treat it was any other rabbinically-prohibited foodstuff for all intents and purposes.