Yes, Teysa is able to get rid of
Progenitus, iran into a similar situation and found by googling around that it's actually valid according to the rules as in fact "everything" is a very poor wording because it does NOT mean everything :
http://media.wizards.com/images/magic/t ... 140601.pdf702.16i “Protection from everything” is a variant of the protection ability. A permanent with protection from everything has protection from each object regardless of that object’s characteristic values.
Such a permanent can’t be targeted by spells or abilities, enchanted by Auras, equipped by Equipment, fortified by Fortifications, or blocked by creatures, and all damage that would be dealt to it is prevented.
Note the key word is "targeted"
114.9. Spells and abilities can affect objects and players they don’t target. In general, those objects and players aren’t chosen until the spell or ability resolves. See rule 608, “Resolving Spells and Abilities.”
114.9a Just because an object or player is being affected by a spell or ability doesn’t make that object or player a target of that spell or abi lity. Unless that object or player is identified by the word “target” in the text of that spell or ability, or the rule for that keyword ability, it’s not a target.
114.9b In particular, the word “you” in an object’s text doesn’t indicate a target
And
Teysa, Envoy of Ghosts does not have the word target, so her ability is not considered as using a target according to that rule and so that's how it can get through the "protection against everything" from
Progenitus.
Because that's the flaw with those wording "everything" does not mean "everything", it only mean "everything using target" or block or combat damage.
It's a bit like
Wrath of God that destroy every creatures even those with hexproof or shroud (and will destroy
Progenitus too) , because of the wording is "destroy all creature", it does not have the word target or targeted and will then ignore the anti-target protection of shroud or hexproof, only creatures with "indestructible" are immune because
Wrath of God has the word "destroy", it would have "remove" instead then the "indestructible" creature would be removed