Locke is a great character. <3 Though I don't think intimacy with him would be all that different, at least not if you're referring to what types of cybernetics he has. Aside from his arms, most of his cybernetics are internal - though he has some other external pieces down the sides of his legs/hips. I guess since you only ever see him clothed, it gives the impression that his entire body is cybernetic, but it's not. In any case it wouldn't matter that much. Lance is more cybernetic than Locke is. LoL!
I think it would be interesting to explore a story involving Locke finding Morgan instead of Quill, though. But you're right that the overall plot might end up being pretty similar. It would be the romantic development that would flow differently.
As far as Locke and Vanessa meeting - I don't think it would be that interesting. Locke knows tons of cybernetic augments like himself. I doubt he'd even pay much attention to Van if they met, honestly.
As for how she maintains citizenship - Van is just under the biosynth threshold, but it wouldn't matter. Braesil has different biosynth policies than New Albion anyway.