The two people on whom it worked, of a group of vikings and a group of hedonistic people, were the Christian missionary and Aud's "father". Most sects of Christianity prefer that their clergy not have sex, and usually make it a requirement, so that covers Harald. As for King Arnulf, he is a very naive and gullible married man whose wife had a cloak of invisibility that worked only on him, and if the guess is correct, it would cease to work on him if he ever lost his virginity. Think about it.
Viking, dark hair, marries an easy going guy, and has a rather relaxed attitude towards sex? She's clearly the same Aud who is to become Anyanka the Vengence Demon. Plus, it would be awesome.