In a way or another, the love between Keisaku and Margery is somewhat similar to the one between Johan and Pheles. Remember that when Johan announced his love to Pheles, he was still a human. Again, the age of immortal Pheles is not a factor. Furthermore, Pheles know Johan even since he was just a baby and took care of him until he grew up. Well, falling in love with someone you know since he was just a baby is not really a problem, since they are all immortal.
