This past-life story is one of eight told by the Bodhisatta in the Kunala Jataka (#536) as examples of why men should never trust women.
The Bodhisatta was once a king. His beloved queen consort took a palace servant as a lover. After the Bodhisatta fell asleep, she would climb out the window to meet him; then when she returned to their room she’d wash up and go back to bed. One night the Bodhisatta noticed her body was cold under the covers and he got suspicious. So the next night he pretended to fall asleep, followed her when she left, and saw her getting intimate with the servant.
The next day the Bodhisatta summoned the queen and exposed her affair in front of his advisors. Though her offence deserved death, mutilation, or imprisonment, because all women are sinners the Bodhisatta just stripped her of her high rank and chose another chief queen.
In the Lifetime of the Buddha
Five hundred new disciples of the Buddha felt dissatisfied. They had ordained following a quarrel between the Buddha’s Sakya clan and a neighboring clan over who should get water for their crops when their shared dam ran low at the end of the dry season. The Buddha convinced everyone to settle their dispute peacefully, and as an act of atonement for planning to go to war, each of the clans sent two hundred fifty princes to become disciples. But these men had ordained out of respect for the Buddha, not a desire for spiritual growth, and feelings for their former wives led to discontent. To help them overcome their dissatisfaction, the Buddha told them this story about the momentous sermon on the inherent wickedness of women he had given when he was a cuckoo in an earlier birth, and the sermon included this particular story.