Very glad to see that other people agree with my ages-old theory that Gin and Shiho had some sort of relationship in the past, but, IMO, what I got from all of the hints is that the relationship was merely sexual. I don't think of Gin as the kind of person to even have love as an emotion, and considering Shiho's personality as well, it may be that in the past, they were actually lovers, hence Gin's obsession with finding and killing her, since that's the only thing he's ever felt and shred of feelings for.