If you play Magic: the Gathering Conflux, then Progenitus is still out there! It is one of the ULTIMATE win cards in Magic. It’s abilities include: Protection from everything, and if it is sent to the graveyard instead it is just shuffled back into it’s controller’s deck… and it’s a 10/10 creature. Wow… As if that isn’t over-powered. If you don’t have the right cards in hand to fight it, it’s game over. Of course to many, the paranoia of making deck changes just to prevent death by Progenitus isn’t worth. So what? You lose ONE game in the case that your opponent manages to get enough mana (2 of everything), and also happens to draw the card.
If your opponent is like myself and knows how to make a 1337 Progenitus deck, the card has a decent chance. So, for the sake of everyone out there who has a friend who always kills you with his/her Progenitus, know that there is hope, and that this hope is actually by the help of common cards!
One way to kill Progentius is the use of Sudden Spoiling from the Time Spiral expansion (Oct 6, 2006). Because Sudden Spoiling does not target Progenitus, but targets all of your target’s creatures, it will work to weaken it if you have a creature that could send a 10/8 Progenitus with no protection to the graveyard. However, I believe Progenitus would then still be shuffled back into your opponent’s deck since once in the graveyard Sudden Spoiling would not be affecting it anymore and Progenitus‘ abilities are then reactivated. Same if by chance the 7 cards discarded from a Nicol Bolas Planeswalker (Conflux) happen to include a non-played Progenitus, it would just get shuffled back into the owner’s deck. I do realize this card is a rare and a mythic rare, and I just said you can destroy Progenitus with commons… But sit tight! There’s more!
Waait for it…. And here it is! We know the key to killing Progenitus is indirect targeting, and the only way to keep it from coming back would have to be removal from the game. Anything targeting Progenitus directly will be inaffective, but if it is a card such as Wrath of God (7th or 10th Ed.) or Cruel Edict (Portal II, 9th, or 10th Ed.), that will work. Wrath of God destroys all creatures (including your own, unfortunately) and Cruel Edict, if you’re lucky, will force your opponent to destroy the mighty Progenitus by his/her own hand!
So, hopefully you play a deck with Swamp or Plains in it. However, there may be other ways with other cards too. I know there are cards where if you know what powerful cards your opponent has you can call them out, such as Meddling Mage from Alara Reborn. She only works if Progenitus is not on the field since its protections are only up once its played. I haven’t really looked into any of the M2010s or new expansions, but the rule is: no direct targeting FTW! Enjoy 
