Governments should just bill the manufacturer and the airline for the costs of the search and rescue/recovery operation. Then the manufacturers, airlines, and their insurers could work out what the cost/benefit equation is.
That would fix the economic incentives, but not the larger externalities. After all, many black boxes are never recovered[1], including the Eastern Airlines one at issue (well, it might have just been recovered, decades late) and, so far, MH370's. To an airline, this outcome is not the end of the world, or perhaps even preferable: abstractly, data from the flight recorder might help prevent future crashes, but that's far in the future, the crash rate is already very low, and in the near term, whenever info about the crash makes it into the news cycle, that's bad PR for the airline. But the government has a strong interest in getting that data: if it was terror, that information can help catch the masterminds and prevent future attacks; if it was an accident, well, government regulatory bodies are the embodiment of the public's collective interest in safety, which is considered more important than short-term profit. On top of that, typically, people who knew the victims have a very strong emotional interest in learning what happened, no matter whether any practical benefit can be derived from the knowledge.
If there was some realistic dollar amount that would guarantee recovery of existing black boxes, then sure, bill the airline for it and let them weigh the probabilities. But there isn't. The only way to prevent these types of situations from happening again is by upgrading the technology, and that has to be done in advance.
Of course, that doesn't mean we are supposed to disregard the cost of reducing externalities; nobody wants a bankrupt industry. Me, I'm not familiar with the economics of aviation, so I don't know whether the airlines should, or whether the government should require them to, make those upgrades in the near term. But at the very least, both of those statements will be true someday (due to turnover, technology improvements, etc.), and economic benefits won't have much to do with it.
