Give a special logo/color/background to the premium stickers or to premium users (people paying 1€/month for example).

I think algorithmically detecting paid stickers on upload can work. I needed to detect duplicate images for a pet project once and I've got satisfying results out of using perceptual image hashing. Building up a database of hashes for existing files takes time, but after that looking up an image to see if it's in the database is fast, and it handles some basic color transforms, as well as minor cropping.

I'm not sure whether this particular approach is feasible at the scale of Telegram. But I believe this arrangement can be a good income source without upsetting users the way ads might.