If the sticker is not easily removable, it would likely fall under defacement of the mail which is illegal according to 18 U.S. Code § 1705 - Destruction of letter boxes or mail:
Whoever willfully or maliciously injures, tears down or destroys any letter box or other receptacle intended or used for the receipt or delivery of mail on any mail route, or breaks open the same or willfully or maliciously injures, defaces or destroys any mail deposited therein, shall be fined under this title or imprisoned not more than three years, or both.
They do not have the right to deface your mail while they are holding it for you, and just because it's not inside an actual mailbox because it doesn't fit is not an exception. However, that requires arguing that a sticker is actually defacement. If it can easily be removed, like a sticky note, then you likely won't win that argument.
In fact, many universities which must handle mail services for students advise that rubber banding a note around the mail is acceptable, as is writing student information onto the mail. So complaining about the sticker would likely just cause them to attach it in a different way that does not qualify as defacement. You can't completely stop them from advertising their stuff, and it's really not much different than if they had gone around and put a door hanger on all of your doors.
