Do the secondary effects of protection from evil prevent a Programmed Amnesia spell

Pathfinder states that each spell of the Enchantment school as well as each Pattern and Phantasm spell in the Illusion school is Mind-Affecting. See Mind-Affecting^D20PFSRD definition and the Magic^D20PFSRD chapter for reference.

Mind-Affecting
Enchantment spells affect the minds of others, influencing or controlling their behavior. A mind-affecting spell works only against creatures with an Intelligence score of 1 or higher.
All enchantments, illusion (patterns), and illusion (phantasms) are mind-affecting.

So it seems more like a definition of the Enchantment school instead of the definition of the Mind-Affecting descriptor.

Protection from Evil, as you pointed out does not mention the Mind-Affecting descriptor, but states that:

[...] the subject immediately receives another saving throw (if one was allowed to begin with) against any spells or effects that possess or exercise mental control over the creature (including enchantment [charm] effects and enchantment [compulsion] effects). [...]

If we accept these two assumptions:

1. The Mind-Affecting definition does not only refers to Enchantment and Illusion spells (and the Necromancy-tied Fear seems to suggest so).
2. An effect with the Mind-Affecting descriptor is eligible to get a second saving throw under a Protection from Evil spell.

Then the answer is Yes.

Note that this answer specifically address your citation of the Fear's Mind-Affecting descriptor. One could also argue that, as long as the Protection from Evil wording is concerned, a Fear actually triggers the abjuration spell's condition outright because - in fact - it exercise influence over the target's course of action.

Looking through the rules, it seems that by a lawyerly reading of MCaE, the "protection" version of the spell (as opposed to the "prison" version; more on this in a moment) essentially has two effects: a mass PoE, and a circle that certain summoned creatures cannot enter.

The mass-PoE effect seems to be essentially unaltered from the original spell, except that it only applies to creatures inside the circle. If you walk outside, you lose the effect; if you walk back inside, you get it again. This makes the personal protection against bodily contact a moot point. One could argue that it technically still exists, but it only applies while you are in the circle, where there is already another barrier in place. Because the circle is not linked to you specifically, it does not collapse if you reach across the circle to attack.

Speaking of reaching across the circle, both PoE and MCaE are very explicit that they only apply to the creatures themselves. Ranged attacks are fair game. Even an imprisoned creature, in the "prison" version of the spell, is explicitly stated to be able to make ranged attacks across the circle, as long as they don't target the circle itself. So yes, creatures inside an MCaE can make ranged attacks across it, but so can creatures outside an MCaE.