My opponent casts Bribery, selects one of my creatures, and it comes into the battlefield under his control.
I cast Treachery (or some equivalent, like Control Magic) on that creature. It comes to my control.
My opponent destroys the enchantment (Treachery, Control Magic, whatever) with something like Naturalize, Vindicate, whatever.
Under whose control is that creature now? His/hers?
Your opponent's. There are two control effects on the creature after you cast Treachery. Once that control effect ends, the other takes effect again. It doesn't matter that you own the creature. All that matters is that the first control effect is the one granting your opponent control of the creature so it will be the one the game "defaults" to if there are no later control effects acting on the creature.
When the creature from your library enters the battlefield it enters under your opponents control. So when you cast your aura to gain control of said creature you would have the most recent control effect for that creature. However once that effect ends (due to the aura being destroyed) it returns to the player who then has the most recent control effect, which would be your opponent.
Bribery doesn't actually create a control effect. It puts the creature onto the battlefield under the player's control, which makes that player the creature's default controller.
110.2. A permanent's owner is the same as the owner of the card that represents it (unless it's a token; see rule 110.5a). A permanent's controller is, by default, the player under whose control it entered the battlefield. Every permanent has a controller.
110.2a. If an effect instructs a player to put an object onto the battlefield, that object enters the battlefield under that player's control unless the effect states otherwise.
When the Treachery goes away, there are no control effects affecting the creature, so it is controlled by its default controller.
My opponent casts Bribery, selects one of my creatures, and it comes into the battlefield under his control.
I cast Treachery (or some equivalent, like Control Magic) on that creature. It comes to my control.
My opponent destroys the enchantment (Treachery, Control Magic, whatever) with something like Naturalize, Vindicate, whatever.
Under whose control is that creature now? His/hers?
When the creature from your library enters the battlefield it enters under your opponents control. So when you cast your aura to gain control of said creature you would have the most recent control effect for that creature. However once that effect ends (due to the aura being destroyed) it returns to the player who then has the most recent control effect, which would be your opponent.
When the Treachery goes away, there are no control effects affecting the creature, so it is controlled by its default controller.