I suppose the problem is that you cannot satisfy everyone and that no matter what someone will complain. I think its going to be one of those situations where everyone is going to have a different take. I think, at least, my concept might be a way to add more variety without bloating the existing trees beyond their current state.
I think between our two approaches, they could converge into excellent reasoning behind a Sister being there and in what form they would take. I do think the Novitiate approach would be the best starting point for them in regards to gear/equipment, especially as you cannot just let them have Power Armour and Bolt weapons off the bat. The idea of having an order based around Messelina, most likely founded on Messelina Gloriana itself (or possibly Crucis, as that is the bigger Shrine World) is perfect and I applaud your pointing out that premise.
I can see why you would suggest a non-Militant Order, as otherwise they would most likely already be helping Grendyl out, Hereticus and all that. Alternatively, it could still be a Militant one but is so heavily committed to the Fringe Wars that it cannot extricate to help Grendyl or even knows to come to his aid. Instead, they send what few Novitiates they have in training to aid Grendyl in supplementing the Rejects already gathered up. Either way, this would set solid ground for the character backstories as you point out.
Mechanically, thinking of the Faith concept, perhaps their special is an inversion of how it is currently handled; you build to your Ability and then spend it, although precisely how is beyond my ken.
Either way, perhaps such a conversation is probably beyond the boundary of this thread and it would be apt to start a SoB thread like the one focused on the possibility of introducing Ad Mech.