Looking at addresses, I've run into both CP or Case Postale, as well as BP, or Boîte Postale. Are the terms interchangeable? Does this vary by country?
Case Postale (CP) is used in Canada and in Switzerland.
Boite Postale (BP) is used in France and in Belgium.
They represent the same service, i.e. a locker (box) situated on the premises of a post office building and that an individual rents to have his mail addressed to.
They are not interchangeable in France :
Case postale and boîte postale are synonyms and are both correct. What is similar but improper in that sense is casier postal.
Le Petit Robert lists case postale as a regionalism, so it is probably better to use boîte postale in France, but it is used elsewhere. For example, Canada Post recommends using case postale, but both are accepted.
"Case postale" has been used for at least some years by Canada Post as its official term for "post office box" in French (not entirely sure why they changed though), although "boîte postale" remains in common use.