In that situation, I guess there's not much power Company A has with regards with Company B, right? Unless Company B is worried that they'll have a future relationship and thus will be willing to submit some kind of audit.
Zuck's announcement seems to have a decent outline -- start with investigating apps with access to large amounts of data, audit apps with strange behavior. But after a year, after the CA (and other) controversies are forgotten, what I was thinking was that FB should be doing regular, random audits/investigations, and publicize the punishment.
I don't mean identifiable shaming, e.g. "Last week, we banned Jane Smith and her Flappy Farm app for misusing the data of 3,000+ users". But maybe weekly/monthly tallies of apps that were shut down or sanctioned, and a breakdown of the reasons why, and users affected, etc. Every once in awhile, an app maker might post a "We Fucked Up" article on HN, which helps even more in reminding people of TOS.