I've gone thru a few chars now and all get introduced to Alexandra after Valeria first mission. Doubt it's lack of badges that's the issue since Voltor would have ALL the badges other than maybe the brand new ones.
My guess is there's an Ouro arc (maybe some other task?) that somehow turns off whatever flag gets set to not introduce her. Which arc? Not sure and with my potato of a system, will take a long time to hunt down.
This theory based on Cobalt's mention of the Ouro arc not introducing contacts as expected, but for some reason it's not for certain live chars.
If someone hasn't by the time I can check, I'll try running an Ouro arc, then going to Val right after. My suspicion would be Sister Solaris arc, since that one helps intro Val. Though I know one of my chars did do Sister via Ouro at least once and still got the intro from Val.
edit add: Hmm, RipRend kinda kiboshes the theory right there.