You could negotiate sticker sending by hash: the first message only contains the hash value, if the recipient already has that sticker stored, it can be displayed immediately. Otherwise the full data can be requested.

EDIT: That scheme can be used to probe whether or not someone already has a specific sticker stored, so it might have to be separated per-contact to avoid leakage.