Painter's Servant + Grindstone + Gaea's Blessing

[diopter]

Ok so the cards in question:

Painter's Servant

Artifact Creature - Scarecrow 
1/3 
As Painter's Servant comes into play, choose a color.
All cards that aren't in play, spells, and permanents are the chosen color in addition to their other colors. 

Grindstone

Artifact
, : Put the top two cards of target player's library into that player's graveyard. If both cards share a color, repeat this process.

Gaea's Blessing

Sorcery
Target player shuffles up to three target cards from his or her graveyard into his or her library.
Draw a card.
When Gaea's Blessing is put into your graveyard from your library, shuffle your graveyard into your library.

Now as is being discussed on TMD and SCG, Painter's Servant and Grindstone form an infinite mill combo. As with all infinite mill combos, there are rule issues and confusions when you add an opposing Gaea's Blessing to the mix.

My question is, if I Paint for infinite mill, and my opponent has a Gaea's blessing in their deck, what will happen? My initial impression is that the effect of Grindstone is a single effect so the Gaea's Blessing trigger will have no chance to resolve until all of your opponent's cards are in his graveyard. At which point... your opponent gets to shuffle his cards back? In which case the combo doesn't work against Gaea's Blessing.

Thanks.

[Apollyon]

You start to mill their library. The Blessing will get revealed and the trigger will wait until after the ability has finished and the whole library is milled. Once the library is finished being milled, the ability will end and the trigger goes on the stack. Once it resolves, all of the cards in the graveyard will get shuffled back into the library.

[Thicketman]

Couldn't the blessing be extirpated in the process?

[Wagner]

Couldn't the blessing be extirpated in the process?

Yes, when it goes into the graveyard, its ability is put on the stack and it can be Extirpated, but you will still shuffle your library once the Blessing's trigger resolves.

[Mr. Nightmare]

Couldn't the blessing be extirpated in the process?

Yes, what is goes into the graveyard, its ability is put on the stack and it can be Extirpated, but you will still shuffle your library once the Blessing's trigger resolves.

However, it only requires a single Tormod's Crypt, activated with all the Blessing tiggers on the stack, to remove the library from the game.