For Cabinet or Ministerial level people, you probably wouldn’t go wrong with a simple “Excellency” or “Your Excellency”. (same as 閣下 if I’ve got the right characters.)
“Mr. Prime Minister” doesn’t sound wrong to me either, but usually that would be more for addressing him orally, not in writing, and since Chinese protocol tends to be much more formal than American, I would go with “Excellency”. I don’t think anyone would ever be offended by being (wrongly) called “Excellency” but they might if they should be called “Excellency” and you forgot to do so.
This is not based on any official source, BTW.