Good question. I'm more used to "on the horns of a dilemma." At the risk of being called a Ghit:

On the horns of a dilemma: 142,000

Between the horns of a dilemma: 333