The Constitution in general protects much less when the borders are involved. I meant to say that the US government can open any mail it feels like if that mail

The Constitution in general protects much less when the borders are involved. I meant to say that the US government can open any mail it feels like if that mail isn't a first class letter, without needing permission from a judge. Additionally, even first class letters aren't protected if they cross the border; the government can inspect anything it feels like that crosses a border without needing permission from any judge. Unless someone forged the notice (unlikely, as you point out) some government opened it (it could also have been the government of the sender or any transit country). All those notices are the government voluntarily letting you know because someone in the government thought it would be better; if the FBI wanted to open a package because they vaguely suspected terrorism they could do it without needing to stamp the package or give any notice if they wanted.