> One obvious solution would be a government program whose mission is to identify promising treatments for which private incentives don't line up, and shepherd them through the approval process by funding clinical trials and so on

You already have this. It's called Orphan Drugs in the US. http://en.wikipedia.org/wiki/Orphan_drug

> a free-market variant, in which the government just auctions off US patent rights for foreign drugs

This will probably work. But once the barrier is too low, a lot of "useless" drugs will show up (i.e. providing more choices to prescribers but in reality does not really give much benefit) - and you need to fund those too using the taxpayers' money.