I know that I am absolutely over thinking this but, for example, what happens in this situation:

Power of Faith (all holy characters gain a M icon) is out, a holy character gets hit with a Orphan of the Greenblood to dump the three icons. Since Power of Faith is out and the holy crest is still present on the character, would that character "regain" the M icon? Or am I completely daft?

When you check to see if a character has an icon, you total up all effects.

So, in your example:

Gains a Mil icon via Power of Faith (+1), loses a Mil icon due to Orphan (-1) = 0, no icon

Now lets say you put a Rusted Sword on your character:

Gains Mil icon via PoF (+1), gains Mil icon via Rusted Sword (+1), loses a Mil icon due to Orphan (-1) = 1, has the icon

Ultimately, a character can only ever have 1 of each challenge icon. So the check is only to see if that icon is there, or not.

goshdarnstud said:

Seriously, though, just like STR, you add up all the "gains/loses icons" effects and apply the result to the character. So since you have a "gains 1" and a "loses 1" effect, you add them together to "no net gain or loss," leaving the character with whatever is printed.

The "add all applicable modifiers together and apply the result" rule is basic and applies to pretty much everything that modifies a card - and every characteristic, at that.