I only really know one game in which sex has worked well, besides the aforementioned Heavy Rain, and that would be Baldur's Gate. Especially in the sequal, sexual relations with the other characters had a large impact on how they treated you afterwards. For example, your beautiful drow companion Viconia is a brutal, pretty apathic, unfeeling thing of a woman, but after learning the fate of her family while visiting the Underdark, she feels exposed, and simply afraid. She stretches out to the main character (if you've carried the relationship up 'til this point which wasn't easy in the first place), and confesses all her fears, and her respect for him. (Which in drow society would be quite the blunder, as females are the dominant sex.)
They end up sleeping together, and the morning after; she's distant, and even colder than usual. But over time, she begins to soften up due to this experience, and she starts to learn that it isn't necessarily a bad thing to rely on someone else.
Now, THAT is good story-telling. The game uses the theme sex maturely to further it's characters and their relationships. This is something that's become harder to find in role-playing games, these days as the aspect of virtual porn sort of ridicules the feelings behind the act in the first case. For instance, I'd say the relationships in Dragon Age and in Mass Effect would have seemed a lot more serious if the sex was just implied, rather than giving us virtual boobies. (Don't get me wrong here, I like boobies a lot, but there's a time and a place.)
One other example for a game that uses sex well is the Persona series, and the upcoming "Catherine" by the same company seems promising, as well.