That's interesting. Your game is quite different than mine and some of it seems a bit non-standard for a D&D world, but I can definitely see how the dynamics of your game could lead to many interesting conclusions. Certainly it would lead to differences in views on Paladins! Let's explore a bit--
To expand a little bit, the things that don't really work in my game: the idea that a devil would care more about the law/chaos difference than the good/evil difference (in reality she has as much in common with a demon as she does with a paladin)
This much is actually from the core D&D cosmos, though. Left over from a primordial conflict of Order vs Chaos, with Wind Dukes and Obyriths and other stuff, there's a Blood War between Demons and Devils that will kill each other in a frenzy of hatred. There isn't a Blood War between Baator and Celestia. Also, I think a Fallen Angel who used to be Lawful Good and in any case has the exact same goal as the Paladin (to protect the Lawful nexuses from the Demons) and who fell from grace for it shares more in common with the Paladin than the Demons here.
the idea that a devil could stomach social contact with a paladin
It seems in most games I've seen (and some modules), Evil Outsiders delight in social contact with Paladins. Even if they don't have Anyiel's particular neuroses and are doing it out of completely ill intent, they like to do it because continued Association can make the Paladin fall, peaceful contact is enough to qualify for Blackguard, and they're in a good spot to tempt towards a fall regardless.
the idea that love in any kind of virtuous sense is a valid motivation for evil-subtype outsiders, etc
Love is not always totally and completely virtuous--in fact, it is rarely so. Sometimes, the love exists with a lot of emotional and psychological baggage. This is true for humans too: that's why there's the stereotypical clingy girlfriend with abandonment issues whose self-worth is tied up in feeling that she is being loved--she'll follow her boyfriend anywhere and demand increasingly more time together, though all the while she may still be displaying strong love and affection, emotions you would definitely call love rather than lust. Heck, even a Succubus might be able to be that kind of girlfriend, where for whatever reason initial lust turns into an extremely clingy love. Of course, you're much better off getting rid of her before that, since she's going to take proactive and incredibly evil steps in her clinginess (you're spending time gaming with friends every week? Why not seduce the friends and drain their souls!). Even yochlols, the demonic servants of Lolth, are specifically mentioned as randomly falling in love with mortals and living with them faithfully without ever betraying or hurting them, though the mortal inevitably falls to ruin due to the fact that everyone else knows he's dating a demon.
Surely for Anyiel, it makes even more sense than for the aforementioned demons. She has psychological abandonment issues and she has a void in her soul where once there was the love of others and now only evil remains. But she remembers what it felt like to be loved--it felt incredibly good. Really truly loved by someone of pure heart and spirit, not just someone saying 'I love you' to get in her pants or a Charmed or Dominated enthralled victim commanded to love her. It is not a little bit manipulative, as devils are wont, that she won his love through false pretenses by appearing as a mortal, though in this case it wasn't her initial intention, since she meant to just manipulate him into helping her fight demons and only later fell for him when he starting showing her love.