I really feel that both answers are speculative but strongly claim that they did not, a discerning answer is needed. Not that the question is whether he ever had sex and/or was frequently having involved with an individual.
The truth is there is no canon evidence to imply that he did. There is no canon evidence that he did not. Harry Potter is a world where the sex in the background is not shown to the readers because it is ultimately written for children. We know from canon sources that he never loved a woman, but sex may not equal love and for him to be a virgin, if he does have sexual feelings, would be out of character.
For many people, sex is about power and control. While he loves no one, those are two things he adores. This is especially true of "taking advantage" of a married woman as he is asserting dominance over husband and wife. Metaphorically, it serves same purpose when he took Malfoy's wand.
His father was taken advantage of sexually, that is for certain. By using someone else sexually he is not emulating his father; he is psychologically doing the opposite. I'm not sure that would actually come into play but it was in another answer.
He cares about power and immortality and (while he wouldn't love them) sex gives children and heirs (in someways) provide both. This is a weak argument though as he doesn't have any and the weak reflections of himself would likely disgust him. He probably feels that he is some form of twisted perfection of humanity and any "dilution" with another person would spoil that.
How is it out of character? If he is not asexual, which is comparatively uncommon, he is a man who goes out to take anything he wants. If he has those feelings it would be odd for a character like him not to experiment with them.
Now as an adult, would it be advertised who he sleeping with? No. He likes to portray himself as above the rest of humanity so if he takes part in a human vice, he will have no desire to advertise it. Nevertheless he would not really care what those vermin think about him. Also there is not Public Display of Affection(PDA) if there is no A. So would we know? No.
Would there be any reason he would pick Bellatrix? We don't know but I don't see that as the question. He has no reason to assert dominance on her.
He may have liked to do so on other, more "feisty" individuals like Tonks or Ginny though.