Was Wes Weimer ever considering a Valen/(unredeemed) Sarevok romance? Some of the things she says to him when they first meet are...suggestive, to say the least.
If not, I think it'd be...interesting to watch. And it would solve some of the problems with a Valen/PC romance...for example, while a vampire PC with a dominant vampire NPC wouldn't work from a role-playing perspective (you're the party leader, after all), one NPC dominating another would seem to work just fine.
Of course, Sarevok might have his own ideas about such a subservient relationship (or *any* relationship with Valen; if Viconia scares him...), and as a former Bhaalspawn with a number of mystical powers remaining, it might be hard for Valen to keep him reliably under control... On the other hand, Valen offers power, and power isn't something Sarevok is known to snub. All sorts of interesting conflicts, both between and within characters.
I'm with the people who thing Valen should be unredeemable; if this romance gets underway before a Sarevok redemption, he should become unredeemable too.