For me it happened with three vocaloids: Iroha(lol), Mayu and IA.
For Iroha, I discovered her thanks to a cover with MAIKA (I think). It was a cover of Pink Diva and I simply adored that cover. One day I accidentally pressed, on youtube, Iroha's version instead of MAIKA's and I felt so impressed, that I went on and started to look for more of her songs. Later that day I discovered Shooting Star, and honestly, that was the song that sold Iroha to me
With Mayu, I thought her design was meh, pretty lolita goth generic. The only thing that interested me was her yandere persona. I don't remeber when or how, I just remember that one day I went to youtube and started to listen some of her songs. I feel in love with Ellie and An Earnest Unrequited Love, Waiting to Make It Bear a Little Happiness (what a long ass title) and that was it honestly. My Mayu phase it's over, so I kind of only remember those songs.
About IA, I always thought she was soooo overrated, I honestly couldn't stand her, never understood her appeal at all. So two years ago I listened Six Trillion Years and a Overnight, and well I loved the song, I'm still unimpressed by her voice, but the song kinda of made me more tolerable to her stuff, so yay?
Kinda of a boring tale lol, but it helped me understand why people like her so much.